最短路径——Dijkstra算法和Floyd算法

一、Dijkstra算法

1、单源点的最短路径问题：给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。

我们用一个例子来具体说明迪杰斯特拉算法的流程。

定义源点为 0，dist[i]为源点 0 到顶点 i 的最短路径。其过程描述如下：

第 1 步：从源点 0 开始，找到与其邻接的点：1，2，3，更新dist[]数组，因 0 不与 4 邻接，故dist[4]为正无穷。在dist[]中找到最小值，其顶点为 2，即此时已找到 0 到 2 的最短路。

第 2 步：从 2 开始，继续更新dist[]数组：2 与 1 不邻接，不更新；2 与 3 邻接，因0→2→3比dist[3]大，故不更新dist[3] ；2 与 4 邻接，因0→2→4比dist[4]小，故更新dist[4]为 4。在dist[]中找到最小值，其顶点为 3，即此时又找到 0 到 3 的最短路。

第 3 步：从 3 开始，继续更新dist[]数组：3 与 1 邻接，因0→3→1比dist[1]小，更新dist[1]为 5；3 与 4 邻接，因0→3→4比dist[4]大，故不更新。在dist[]中找到最小值，其顶点为 4，即此时又找到 0 到 4 的最短路。

第 4 步：从 4 开始，继续更新dist[]数组：4 与 1 不邻接，不更新。在dist[]中找到最小值，其顶点为 1，即此时又找到 0 到 1 的最短路。

第 5 步：所有点都已找到，停止。

对于上述步骤，你可能存在以下的疑问：

若 A 作为源点，与其邻接的只有 B，C，D 三点，其dist[]最小时顶点为 C，即就可以确定A→C为 A 到 C 的最短路。但是我们存在疑问的是：是否还存在另一条路径使 A 到 C 的距离更小？ 用反证法证明。

假设存在如上图的红色虚线路径，使A→D→C的距离更小，那么A→D作为A→D→C的子路径，其距离也比A→C小，这与前面所述 “dist[]最小时顶点为 C” 矛盾，故假设不成立。因此这个疑问不存在。

根据上面的证明，我们可以推断出，Dijkstra 每次循环都可以确定一个顶点的最短路径，故程序需要循环 n-1 次。

/* 迪杰斯特拉求单节点到其余各节点的最短路径。 visited数组用于保存顶点是否已经求过最短路径，pre数组用于保存最短路径的下标 dist数组用于保存初始节点到其余节点的最短路径长度。 该算法求有向图G的某顶点到其余节点的最短路径pre以及长度dist pre[v]的值是v0-->...->v的路径中的前驱节点。D[v]表示v0-->...-->v的最短路径长度和。 可以证明迪杰斯特拉算法每次循环可以确定一个顶点的最短路径，所以主程序循环n-1次。 主程序循环主要做两件事：首先找出dist数组中的最小值，并记录下标，说明找到初始点到该下标的最短路径。 然后要比价初始点到该点的最短路径加上这点到其他初始点需要到的点的距离是否比初始点直接到这些点的距离短 如果要短，那么就更新dist数组，并且这些点的前驱节点就会变为v而不是开始的v0点。下一次主循环再去从dist中找 最小的值并且未求过的点，就是该点的最短路径。 */ #include 
  
    using namespace std; int matrix[100][100];//邻接矩阵 bool visited[100];//标记数组 int dist[100];//原点到i顶点的最短距离 int pre[100];//记录最短路径。pre[i]放的是i的前驱节点 int source;//源节点 int vertex_num;//顶点数 int edge_num;//边数 void Dijkstra(int source) { //首先初始化 memset(visited,0,sizeof(visited)); visited[source] = true; for (int i = 0; i < vertex_num; i++) { dist[i] = matrix[source][i]; pre[i] = source; } int min_cost;//最短距离 int min_cost_index;//权值最小的那个顶点的下标。（求好了） //主循环 for (int i = 1; i < vertex_num; i++) { min_cost = INT_MAX; for (int j = 0; j < vertex_num; j++) { //注意要确保这个点没有找过。 if (visited[j]==false&&dist[j] < min_cost) { min_cost_index = j; min_cost = dist[j]; } } visited[min_cost_index] = true;//找到某一个点的最短距离 //利用该点进行dist的更新，并且调整前驱。 for (int j = 0; j < vertex_num; j++) { //确保有连接 if (visited[j] == false && matrix[min_cost_index][j] != INT_MAX&&min_cost+ matrix[min_cost_index][j] < dist[j]) { dist[j] = min_cost + matrix[min_cost_index][j]; pre[j] = min_cost_index; } } } } int main() { cout << "请输入图的顶点数（<100）:"; cin >> vertex_num; cout << "请输出图的边数: "; cin >> edge_num; for (int i = 0; i < vertex_num; i++) { for (int j = 0; j < vertex_num; j++) { matrix[i][j] = (i != j) ? INT_MAX : 0; } } cout << "请输入边的信息：\n"; int u, v, w; for (int i = 0; i < edge_num; i++) { cin >> u >> v >> w; matrix[u][v] = matrix[v][u] = w; } cout << "请输入源点(<" << vertex_num << "): "; cin >> source; Dijkstra(source); for (int i = 0; i < vertex_num; i++) { if (i != source) { //路径是反的，从目标点向前不断找前驱的过程。 cout << source << "到" << i << "最短距离： " << dist[i] << ",路径是：" << i; int t = pre[i]; while (t != source) { cout << "--" << t; t = pre[t]; } cout << "--" << source << endl; } } return 0; } 
  

二、Floyd算法

暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。

上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。

我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4号城市到3号城市（4->3）的路程e[4][3]原本是12。如果只通过1号城市中转（4->1->3），路程将缩短为11（e[4][1]+e[1][3]=5+6=11）。其实1号城市到3号城市也可以通过2号城市中转，使得1号到3号城市的路程缩短为5（e[1][2]+e[2][3]=2+3=5）。所以如果同时经过1号和2号两个城市中转的话，从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。好，下面我们将这个问题一般化。

for(i=1;i e[i][1]+e[1][j] ) e[i][j] = e[i][1]+e[1][j]; } } 

接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。

//经过1号顶点 for(i=1;i e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j]; //经过2号顶点 for(i=1;i e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j]; 

for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; 

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。其实这是一种“动态规划”的思想，关于这个思想我们将在《啊哈！算法2——伟大思维闪耀时》在做详细的讨论。下面给出这个算法的完整代码：

#include 
  
    int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf=; //用inf(infinity的缩写)存储一个我们认为的正无穷值 //读入n和m，n表示顶点个数，m表示边的条数 scanf("%d %d",&n,&m); //初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; //读入边 for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2]=t3; } //Floyd-Warshall算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j] ) e[i][j]=e[i][k]+e[k][j]; //输出最终的结果 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%10d",e[i][j]); } printf("\n"); } return 0; } 
  

有一点需要注意的是：如何表示正无穷。我们通常将正无穷定义为，因为这样即使两个正无穷相加，其和仍然不超过int类型的范围（C语言int类型可以存储的最大正整数是）。在实际应用中最好估计一下最短路径的上限，只需要设置比它大一点既可以。例如有100条边，每条边不超过100的话，只需将正无穷设置为10001即可。如果你认为正无穷和其它值相加得到一个大于正无穷的数是不被允许的话，我们只需在比较的时候加两个判断条件就可以了，请注意下面代码中带有下划线的语句。

//Floyd-Warshall算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][k] 
  
    e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; 
  

上面代码的输入数据样式为：

4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12