本文最后更新于302 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com
在网图与非网图中，最短路径的含义是不同的。由于非网图没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上第一个顶点是源点，最后一个顶点是终点。
1.迪杰斯特拉（Dijkstra）算法
迪杰斯特拉算法实现过程如下：
首先，顶点0到其它各顶点之间的权值和：
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 总权值 | 2 | 6 | ∞ | ∞ | ∞ | ∞ |
| 路径 | 0-1 | 0-2 | 0-3 | 0-4 | 0-5 | 0-6 |
∞ 表示两个顶点之间无法直达，对应的权值为无穷大。
表 1 中，权值最小的是 0-1 路径，它也是从顶点 0 到顶点 1 的最短路径。原因很简单，从顶点 0 出发一共只有 0-1 和 0-2 两条路径，0-2 的权值本就比 0-1 大，所以从 0-2 出发不可能找得到比 0-1 权值更小的路径。
找到最短路径 0-1 后，沿 0-1 路径方向查找更短的到达其它顶点的路径，并对表进行更新。
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 总权值 | 2 | 6 | 2+5 | ∞ | ∞ | ∞ |
| 路径 | 0-1 | 0-2 | 0-3 | 0-4 | 0-5 | 0-6 |
更新后的表格后，沿 0-1 路径可以到达顶点 3，且 0-1-3 的总权值比 0-3 更小。表中，总权值最小的路径是 0-2，它也是从顶点 0 到顶点 2 的最短路径，如下图所示。
重复之前的操作，沿 0-2 路径方向查找更短的到达其它顶点的路径。遗憾地是，从顶点 2 只能到达顶点 3，且 0-2-3 的总权值比表中记录的 0-1-3 更大，因此表中记录的数据维持不变。
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 总权值 | 2 | 6 | 2+5 | ∞ | ∞ | ∞ |
| 路径 | 0-1 | 0-2 | 0-3 | 0-4 | 0-5 | 0-6 |
表中，总权值最小的是 0-1-3，它也是顶点 0 到顶点 3 的最短路径。
沿 0-1-3 路径方向，查找到其它顶点更短的路径并更新表 3。更新后的表格为：
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 总权值 | 2 | 6 | 2+5 | 7+10 | 7+15 | ∞ |
| 路径 | 0-1 | 0-2 | 0-1-3 | 0-1-3-4 | 0-1-3-5 | 0-6 |
表中，总权值最小的是 0-1-3-4，它是顶点 0 到顶点 4 的最短路径。
从顶点 4 出发，查找顶点 0 到其它顶点更短的路径并更新表，更新后的表格为：
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 总权值 | 2 | 6 | 2+5 | 7+10 | 7+15 | 17+2 |
| 路径 | 0-1 | 0-2 | 0-1-3 | 0-1-3-4 | 0-1-3-5 | 0-1-3-4-6 |
表中，总权值最小的路径是 0-1-3-4-6，它是顶点 0 到顶点 6 的最短路径。
从图中可以看到，只剩下顶点 0 到顶点 5 的最短路径尚未确定。从顶点 6 出发到达顶点 5 的路径是 0-1-3-4-6-5，对应的总权值为 25，大于表 5 中记录的 0-1-3-5 路径，因此 0-1-3-5 是顶点 0 到顶点 5 的最短路径。
由此借助迪杰斯特拉算法，我们找出了顶点 0 到其它所有顶点的最短路径，如下表所示：
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 总权值 | 2 | 6 | 7 | 17 | 22 | 19 |
| 路径 | 0-1 | 0-2 | 0-1-3 | 0-1-3-4 | 0-1-3-5 | 0-1-3-4-6 |
迪杰斯特拉（Dijkstra）算法代码实现：
#include<iostream>
using namespace std;
#define MAXVEX 20
typedef struct {
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes;
int numEdges;
}MGraph;
typedef int Patharc[MAXVEX]; //存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX]; //存储到各点最短路径的权值和
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=9;
G->numVertexes=7;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = 65535;
}
}
G->arc[0][1]=2;
G->arc[0][2]=6;
G->arc[1][3]=5;
G->arc[2][3]=8;
G->arc[3][4]=10;
G->arc[3][5]=15;
G->arc[4][5]=6;
G->arc[4][6]=2;
G->arc[5][6]=6;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
//Dijkstra算法，求有向网图G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]
//P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和
void ShortestPath_Dijkstra(MGraph G,int v0,Patharc *P,ShortPathTable *D){
int v,w,k,min;
int final[MAXVEX]; //final[w]=1表示求得顶点v0至vw的最短路径
for(v=0;v<G.numVertexes;v++){
final[v] = 0; //全部初始化为未知最短路径状态
(*D)[v] = G.arc[v0][v]; //将与v0点有连线的顶点加上权值
(*P)[v] = -1; //初始化路径数组P为-1
}
(*D)[v0] = 0;//v0到v0的路径为0
final[v0] = 1;// v0到v0不需要求路径
//开始主循环，每次求得v0到某个顶点V的最短路径
for(v=1;v<G.numVertexes;v++){
min = 65535;//当前所致离v0顶点的最近距离
for(w=0;w<G.numVertexes;w++){
if(!final[w] && (*D)[w] <min){
k = w;
min = (*D)[w];//w顶点离v0顶点更近
}
}
final[k] = 1;//将目前找到最近的顶点置为1
//修正当前最短路径及距离
for(w=0;w<G.numVertexes;w++){
//如果经过v顶点的路径比现在这条路径的长度短的话
if(!final[w] && (min+G.arc[k][w]<(*D)[w])){
//说明找到了更短的路径，修改D[w]和P[w]
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}
}
}
int main(void)
{
int i,j,v0;
MGraph G;
Patharc P;
ShortPathTable D;
v0=0;
CreateMGraph(&G);
ShortestPath_Dijkstra(G, v0, &P, &D);
cout<<"最短路径如下："<<endl;
for(i=1;i<G.numVertexes;++i)
{
cout<<"v"<<v0<<" - v"<<i<<" : ";
j=i;
while(P[j]!=-1)
{
cout<<P[j];
j=P[j];
}
cout<<endl;
}
cout<<"源点到各顶点的最短路径长度为:"<<endl;
for(i=1;i<G.numVertexes;++i)
cout<<"v"<<G.vexs[0]<<" - v"<<G.vexs[i]<<" : "<<D[i]<<endl;
return 0;
}
2.佛洛伊德（Floyd）算法
Floyd算法是一种利用动态规划的思想求带权图中每一对顶点之间的最短距离和最短路径的方法。
首先，我们先按照图中所示，记录各顶点与其直达顶点之间的距离。
然后我们通过依次将任一顶点加入到某一对顶点之间，看时候存在更短的路径到达某个顶点。
佛洛伊德算法代码实现：
#include<iostream>
using namespace std;
#define MAXVEX 20
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = 65535;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
//Floyd算法，求网图中各顶点v到其它顶点w的最短路径P[v][w]及带权长度
void ShortestPath_Floyd(MGraph G,Patharc *P,ShortPathTable *D){
int v,w,k;
//初始化D和P
for(v=0;v<G.numVertexes;++v) {
for(w=0;w<G.numVertexes;++w){
(*D)[v][w] = G.arc[v][w];//D[v][w]值即为对应点间的权值
(*P)[v][w] = w;//初始化P
}
}
for(k=0;k<G.numVertexes;++k){
for(v=0;v<G.numVertexes;++v){
for(w=0;w<G.numVertexes;++w){
if((*D)[v][w]>(*D)[v][k]+(*D)[k][w]){
//如果经过下标为k的顶点的路径比原两点间的路径更短
(*D)[v][w] = (*D)[v][k] +(*D)[k][w];//将当前两点间权值设为更小的一个
(*P)[v][w] = (*P)[v][k];//路径设置为经过下标为k的顶点
}
}
}
}
}
int main(){
int v,w,k;
MGraph G;
Patharc P;
ShortPathTable D; //求某点到其余各点的最短路径
CreateMGraph(&G);
ShortestPath_Floyd(G,&P,&D);
cout<<"各顶点间最短路径如下:"<<endl;
for(v=0; v<G.numVertexes; ++v)
{
for(w=v+1; w<G.numVertexes; w++)
{
cout<<"v"<<v<<"-v"<<w<<" weight: "<<D[v][w]<<" ";
k=P[v][w]; //获得第一个路径顶点下标
cout<<" path: "<<v; // 打印源点
while(k!=w) //如果路径顶点下标不是终点
{
cout<<" -> "<<k;//打印路径顶点
k=P[k][w]; //获得下一个路径顶点下标
}
cout<<" -> "<<w<<endl;//打印终点
}
cout<<endl;
}
cout<<"最短路径D"<<endl;
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
//printf("%d\t",D[v][w]);
cout<<D[v][w]<<"\t";
}
cout<<endl;
}
cout<<"最短路径P"<<endl;
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
cout<<P[v][w]<<" ";
}
cout<<endl;
}
return 0;
} 
