虽然笔者在“算法-图论”的专栏中已经讨论过有关最短路径的问题，但是这里还是重新讨论一下，孔子也说过嘛，温故而知新。
所谓最短路径问题，就是基于一个图G<V、E>，图的边集E是带权的，然后讨论寻求某条连通两个点的路径，使得这条路径是所有连通该路径中边权最小的。
找到任意两点间的最短路径——Floyd-Warshall算法。
这个算法是个本科念文学后来转计算机并于1978年荣获图灵奖的Robert W.Floyd和Stephen Warshall于1962同时独立开发出来的，因此为了纪念他们，该算法融合了两个人的名字。
其实这个算法说来思路也非常简单，我们当前想要求得G中vi到vj的最短路径，最简单暴力的方法是找到vi到vj所有可走的路径，然后维护一个最小值即可。然而现在问题是如何找到这所有的路径？我们找一个中间变量k，vi->vj的路径可以分解成vi->vk 、vk->vj的路径，而将k遍历[i,j]便可枚举出所有情况，你可能会问那vi->vk还有很多路径呢，那岂不还要继续找？事实上，我们设置e[i][j]记录vi->vj的最短路径，而vi->vk、vk->vj则也是基于e[i][k]、e[k][j]的，这样我们其实是枚举了一系列相对最优的情况，然后找到这些相对最优解中的当前最优解的情况，这便是动态规划思想所体现的地方。
本质上讲，该算法是枚举和动态规划的一个巧妙的结合。
#include<cstdio> using namespace std; int main() { int e[10][10] , k , i , j , n , m , t1,t2,t3; int inf = 9999999; 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; } 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]) //Floyd-Warshall算法的核心部分 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(" "); } return 0; }
求解单源无负权的最短路径——Dijkstra算法：
我们从该算法的限制条件出发，既然是无负权，我们能够发现，如果我们筛选与源头s直接相连的点，便可以直接找到源头s到某点的最短路径(因为无负权边，则不可能出现中转点)，我们基于选出来的这个点，假设其为vi，访问与vi直接相连的点vj、vk、vm……，则我们当前可以得到源头s到vj、vk、vm的一条路径，此时我们需要记录下路径<s,vj>、<s、vk>、<s、vm>的权重。然后我们继续遍历与源头s直接相连的点(显然第一次筛选出来的点需要标记访问过，在这次筛选中边不再访问)，然后重复上述步骤……这样的操作进行n - 1次，将确保得到源头到每个点的每条路径，我们只需在访问时维护最小值即可。
以上是对该算法比较模糊和概括性的描述，不难看出，其算法本质是一种巧妙的穷举，然后在穷举的过程中完成对最短路径的记录。
下面我们来描述一下该算法比较量化、精细的描述。
step1：将所有的顶点分为两部分：访问过的顶点放入Q，未曾访问过的顶点放入P。一开始源头s在Q中。
step2:用dis[i]表示第i个顶点到源头的最短路径，访问点集V，满足vi∈P 并且vi与源头s直接相连，找到min<s,vi>，标记vi访问过并记录i和dis[i]。
step3：访问点集V1，对于vj∈V1,满足step2中记录的vi与vj直接相连，此时可访问一条路径<s,vj>，记录dis[j]。
step4：进行step2，直到P是空集。
简单的参考代码如下。
#include<stdio.h> int main() { int e[10][10] , dis[10] , book[10] , i , j , n, m , t1,t2,t3,u,v,Min; int inf = 9999999; 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; } for(i = 1;i <= n;i++) dis[i] = e[1][i]; for(i = 1;i<=n;i++) book[i] = 0; book[1] = 1; for(i = 1;i <= n-1;i++) //筛出当前没有访问的并且与源头直接相连的全职最小的点。 { Min = inf; for(j = 1;j <= n;j++) { if(book[j] == 0&& dis[j] < Min) { Min = dis[j]; u = j; } } book[u] = 1; for(v = 1;v <= n;v++) //边松弛 { if(e[u][v] < inf) { if(dis[v] > dis[u] + e[u][v]) dis[v] = dis[u] + e[u][v]; } } } for(i = 1;i <= n;i++) printf("%d ",dis[i]); return 0; }
解决含负权图的Bellman-Ford算法：
其实从最本质上来讲，最短路径都是某种程度的穷举和动态规划的结合，只是在不同的算法中呈现出不同的方式。
给出一个含负权的有向图，我们如何求解各点到某一点(即单源最短路)的最短路径呢？Bellman-Ford给出了一个非常简洁的方法。
我们利用dis[i]表示vi到源头v1的最短路，用s[i]、e[i]分别记录第i条边的起点和终点，用w[i]记录该边的权值。首先枚举边<s[i] , e[i]>，我们访问dis[e[i]]，并依据这条边的权值来实现边权值，即用一个状态转移方程来表述——dis[e[i]] = min(dis[e[i]] ,dis[s[i]] + w[i])。能够看到，这种状态转移方程要基于dis[s[i]]的确定，而每次枚举边集合，至少能够完成一个点访问和记录，因此对于含有n个节点的图，枚举边集n-1次便可找到源头v1到剩余n-1个点的最短路径。
我们用伪码来描述一下该过程。
fo k 1 to n-1 (n为节点数)
for i 1 to m (m为边数)
dis[e[i]] = min(dis[e[i]] ,dis[s[i]] + w[i]).
简单的参考代码如下。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int main() { int dis[10] , i , k , n , m , s[10] , e[10] , w[10]; int inf = 9999999; scanf("%d %d",&n,&m); for(i = 1;i <= m;i++) scanf("%d %d %d",&s[i],&e[i],&w[i]); for(i = 1;i <= n;i++) dis[i] = inf; dis[1] = 0; for(k = 1;k <= n;k++) for(i = 1;i <= m;i++) dis[e[i]] = min(dis[e[i]] , dis[s[i]] + w[i]); for(i = 1;i <= n;i++) printf("%d ",dis[i]); }