前言

迪杰斯特拉（Dijkstra）算法是基于搜索的路径规划的经典算法之一，可以用于求单源点的最短路径问题，并且算法求解的结果是全局最优的.其基本思想是基于贪心策略，并且具体迭代过程又类似于广度优先搜索（DFS）算法.

一、最短路径问题

在无权网图中，最短路径是指两顶点之间经历的边数最少的路径，路径上第一个顶点称为源点，最后一个顶点称为终点.对于有权网图，最短路径是指两顶点之间的代价最少，根据网图中权值的具体含义而定，如距离、流量、运输成本、时间等.对于路径规划中研究的问题一般都是有权网图，Dijkstra算法是求解单源点最短路径较有效的方法.

1.1 符号说明

$G=\left( V,E \right)$ 表示一个有权图.其中 $V$ 表示图中的顶点集合， $E$ 表示图中的带权边的集合， $E$ 中的每个元素 $e_k$ 表示为 $V$ 中某两个元素 $v_i$ , $v_j$ 的无序对，记为 $e_k=(v_i,v_j)$ .

$c_{i,j}\geqslant 0$ 表示 $v_i$ 和 $v_j$ 之间的代价.

$x_{i,j}\in \left\{ 1,0 \right\}$ 表示决策变量，最短路径是否包含 $v_i$ 和 $v_j$ 之间的路径.

$arc\in R^{\left| V \right|\times \left| V \right|}$ 表示邻接矩阵，其中 $arc\left( i,j \right) =c_{i,j}$ .

$A$ 表示二元有序对集合，可以用于描述一条路径.

$s$ 表示起点， $t$ 表示终点.

1.2 数学模型的建立

起点为 $s$ ，终点为 $t$ 的最短路径的数学规划模型可表示如下：

$\begin{split}&\underset{A}{\min}\,\,\sum_{\left( v_i,v_j \right) \in A}{c_{i,j}x_{i,j}},\\&s.t. \sum_{\left( v_i,v_j \right) \in A}{x_{i,j}}-\sum_{\left( v_j,v_i \right) \in A}{x_{i,j}}=\left\{ \begin{array}{c} \begin{array}{c} \begin{array}{l} 1 , i\,\,=\,\,s,\\ -1, i\,\,=\,\,t,\\ 0 , i\,\,\ne \,\,s, t,\\\end{array}\\\end{array}\\\end{array} \right. \\&\,\, x_{i,j}\in \left\{ 0,1 \right\} .\end{split}$

该问题为 $\left\{ 0,1 \right\}$ 约束线性规划问题，在图的顶点数和边数比较少的情况下可以使用分支定界法来得到全局最优解，但是该算法的时间是指数增长的.但是当问题规模较大的时候这种方法是失效的，所以实际问题中应该考虑更加优越的算法进行求解，其中Dijkstra算法是多项式时间复杂度 $O\left( n^2 \right)$ 的全局搜索算法.

二、Dijkstra算法

该算法就是由出生在鹿特丹（荷兰第二大城市）的狄克斯特拉提出的，由于狄克斯特拉一生中对计算机科学事业的贡献，荣获了1972年的图灵奖.

Dijkstra算法的基本思想是：设置一个集合 $S$ 存放已经找到最短路径的顶点， $S$ 的初始状态只包含源点 $s$ ，对 $v_i\in V\backslash S$ ，假设从源点 $s$ 到 $v_{i}$ 的有向边为最短路径.以后每求得一条最短路径 $s,\cdots ,v_k$ ，就将 $v_{k}$ 加入集合 $S$ 中，并将路径 $s,\cdots ,v_k,v_i$ ，与原来的假设相比较，取路径长度较小者为当前最短路径，如下图所示.

图1. Dijkstra算法的基本思想图解

2.1 Dijkstra算法全局最优解证明

Dijkstra算法迭代的核心思想是基于贪心策略进行的，但是我们知道对于一般问题的的贪心策略求得的解不一定是全局最优的，非常幸运地是，使用Dijkstra算法迭代的就是全局最优的，以下使用反证法来证明.

假设存在一条从源点 $s$ 到顶点 $v_k$ 的最短路径 $D_1$ 比 $D$ 更短，且路径 $D_1$ 经过集合 $V\backslash S$ 中的某些顶点（不妨设为 $p$ ），则路径 $D_1\left( s,v_k \right) =D\left( s,p \right) +D\left( p,v_k \right) <D\left( s,v_k \right)$ ，即 $D\left( s,p \right) <D\left( s,v_k \right)$ ，这与Dijkstra算法按照最短路径长度先把 $v_k$ 挑选出来矛盾！所以使用Dijkstra算法加入集合 $S$ 中的顶点 $v_k$ 一定是 $V\backslash S$ 集合中到源点 $s$ 具有最短路径长度的顶点.

2.2 Dijkstra算法伪代码与流程图

图2. Dijkstra算法伪代码

图3. Dijkstra算法流程图（来自百度）

2.3 Dijkstra算法Matlab实现

问题：某公司在六个城市 $c_1,c_2,...,c_6$ 中有分公司，从 $c_i$ 到 $c_j$ 的直接航程票价记在下述矩阵的 $(i,j)$ 位置上( $\infty$ 表示无直接航路)，请帮助该公司设计一张城市 $c_1$ 到其它城市间的票价最便宜的路线图.

$\left[ \begin{matrix} 0& 50& \infty& 40& 25& 10\\ 50& 0& 15& 20& \infty& 25\\ \infty& 15& 0& 10& 20& \infty\\ 40& 20& 10& 0& 10& 25\\ 25& \infty& 20& 10& 0& 55\\ 10& 25& \infty& 25& 55& 0\\\end{matrix} \right]$

用矩阵 $a_{n\times n}$ ( $n$ 为顶点个数)存放各边权的邻接矩阵，行向量 $pb$ ， $index_1$ ， $index_2$ ， $d$ 分别用来存放在 $S$ 集合的信息， $S$ 集合中顶点顺序， $S$ 集合中顶点索引，最短通路的值.其中：

$pb\left( i \right) =\begin{cases} 1,\text{当第}i\text{顶点已纳入}S\text{集合},\\ 0,\text{当第}i\text{顶点未纳入}S\text{集合}.\\\end{cases}$

$index_2(i)$ 存放始点 $s$ 到第 $i$ 顶点点最短通路中第 $i$ 顶点前一顶点的序号.

$d(i)$ 存放由始点到第 $i$ 顶点最短通路的值.

Matlab代码：

clc, clear;

a = zeros(6);

a(1, 2) = 50; a(1, 4) = 40; a(1, 5) = 25; a(1, 6) = 10;

a(2, 3) = 15; a(2, 4) = 20; a(2, 6) = 25;

a(3, 4) = 10; a(3, 5) = 20;

a(4, 5) = 10; a(4, 6) = 25;

a(5, 6) = 55;

a = a + a';

a(a == 0) = inf;

pb(1 : length(a)) = 0; pb(1) = 1; index1 = 1; index2 = ones(1, length(a));

d(1:length(a)) = inf; d(1) = 0; temp = 1;

while sum(pb) < length(a) %Dijkstra算法终止条件是所有顶点都进入集合S中

tb = find(pb == 0); %V\S集合中的顶点对应下标

d(tb) = min(d(tb), d(temp) + a(temp, tb)); %更新V\S集合中的顶点到源点的距离

tmpb = find(d(tb) == min(d(tb)));

temp = tb(tmpb(1)); %寻找V\S集合中的顶点到源点的最短距离对应的顶点

pb(temp) = 1; %将顶点加入S集合

index1 = [index1, temp];

temp2 = find(d(index1) == d(temp) - a(temp, index1));

index2(temp) = index1(temp2(1));

end

a, index1, index2

2.4 Dijkstra算法C++实现

C++代码：

#include<iostream>

#include<cmath>

#include<cstring>

using namespace std;

const int inf = 0x3f3f3f3f; //代表无穷大

const int maxn = 100; //代表顶点数

int n, m; //n个顶点，m条边

bool visited[maxn]; //判断是否确定到源点的最短距离

int graph[maxn][maxn]; //带权图

int dis[maxn]; //顶点到源点的最短距离

string sline[maxn]; //顶点到源点的最短路径的

int start, goal; //起点和目标点

void init(){

memset(visited, false, sizeof(visited));

dis[1] = graph[start][1];

sline[1] = "1";

for(int i = 2; i <= n; i++){

dis[i] = graph[start][i]; //初始化dis数组

// if(dis[i] != inf){

// char jk = (char)(i + '0');

// sline[i] = "1" + jk; //初始化sline数组

// }else sline[i] = " ";

}

}

void dijkstra(){

//源点为源点start

int minn; //记录每趟最短路径中最小的路径值

int pos; //记录得到的minn所对应的下标

init();

visited[start] = true;

for(int i = 1; i <= n; i++){

//将n个顶点依次加入判断

minn = inf;

for(int j = 1; j <= n; j++){

if(!visited[j] && dis[j] < minn){

minn = dis[j];

pos = j;

}

}

//经过这趟for循环后，我们找到的就是我们想要的点，可以确定

//这点到源点的最终最短距离了

visited[pos] = true; //此点加入已知集合S

//接下来更新dis和sline数组了，也就是当前最短距离，针对还未并入已知集合S的点

for(int j = 1; j <= n; j++){

if(!visited[j] && dis[j] > dis[pos] + graph[pos][j]){

dis[j] = dis[pos] + graph[pos][j];

// cout << (char)(j + '0');

// sline[j] = sline[pos] + (char)(j + '0');

}

}

}

//cout << dis[goal] << endl;

cout << "终点为:" << goal << endl;

cout << "最短路径长度:" << dis[goal] << endl;

// cout << "最优路径：" << sline[goal] << endl;

}

int main(){

while(cin >> n >> m){

memset(graph, inf, sizeof(graph));

int u, v, w;

for(int i = 0; i < m; i++){

cin >> u >> v >> w;

//graph[u][v] = w; //（有向图）距离

graph[u][v] = graph[v][u] = w; //无向图

}

start = 1;

cin >> goal; //输入终点

dijkstra();

}

return 0;

}

路径规划中Dijkstra算法的Matlab和C++实现