图的最短路径算法(Dijkstra，Floyd)的实现

从某个源点到其余各顶点的最短路径

迪杰特斯拉算法

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

算法步骤如下：

初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在，d(V0,Vi)为弧上的权值, 若不存在，d(V0,Vi)为∝从T中选取一个其距离值为最小的顶点W且不在S中，加入S对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的 距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

完整C++代码：

#include <iostream> #include <climits> using namespace std; #define MAX_VERTEX_NUM 20 // 顶点数量上限 typedef char VerType; // 顶点结构 , 顶点的字母名称 typedef int ArcType; // 边的结构 , 权值 typedef enum {DG, UDG} GKind; // 图类型，{有向图,无向图} // 图的存储结构 typedef struct { int verNum, arcNum; // 顶点数量, 边数量 GKind kind; // 图类型 VerType vertex[MAX_VERTEX_NUM]; //顶点 ArcType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //边 }Graph; void CreateGraphByArray(Graph &G); // 创建图G (通过预定义的数组) int VertexLoc(const Graph &G, const VerType &v); // 获取顶点v在图G中的位置 void ShortestPath_Dijkstra(Graph &G, int k); // 最短路径算法 (迪杰斯特拉算法) int main() { Graph G; CreateGraphByArray(G); ShortestPath_Dijkstra(G, 0); return 0; } void CreateGraphByArray(Graph &G) { G.kind = DG; const int vn = 6; VerType V[vn + 1] = {"012345"}; const int en = 8; VerType V1[en + 1] = {"00012344"}; VerType V2[en + 1] = {"25423535"}; ArcType E[en] = {10,100,30,5,50,10,20,60}; // 输入顶点 G.verNum = vn; for(int i = 0; i < G.verNum; ++ i){ G.vertex[i] = V[i]; } // 初始化邻接矩阵 for(int vi = 0; vi < G.verNum; ++ vi){ for(int vj = 0; vj < G.verNum; ++ vj){ G.arcs[vi][vj] = INT_MAX; } } // 输入边 G.arcNum = en; for(int i = 0; i < G.arcNum; ++ i){ VerType &v1 = V1[i], &v2 = V2[i]; ArcType &e = E[i]; int vi = VertexLoc(G, v1), vj = VertexLoc(G, v2); if(vi == G.verNum || vj == G.verNum){ continue; } if(UDG == G.kind){ G.arcs[vi][vj] = G.arcs[vj][vi] = e; }else{ G.arcs[vi][vj] = e; } } } int VertexLoc(const Graph &G, const VerType &v) { for(int i = 0; i < G.verNum; ++ i){ if(G.vertex[i] == v){ return i; } } return G.verNum; } void ShortestPath_Dijkstra(Graph &G, int v0) { const int N = G.verNum; bool S[N]; // 表示v0到vi的最短路径是否已经确定 int Path[N]; // 表示v0到vi的最短路径上的直接前驱顶点 long long D[N]; // 表示v0到vi的最短路径长度 for(int v = 0; v < N; ++ v){ S[v] = false; D[v] = G.arcs[v0][v]; Path[v] = D[v] != INT_MAX ? v0 : -1; } S[v0] = true; D[v0] = 0; for(int i = 1; i < N; ++ i){ int min = INT_MAX, v; for(int w = 0; w < N; ++ w){ if(!S[w] && D[w] < min){ v = w; min = D[w]; } } if(min != INT_MAX){ S[v] = true; for(int w = 0; w < N; ++ w){ if(!S[w] && (D[v] + G.arcs[v][w] < D[w])){ D[w] = D[v] + G.arcs[v][w]; Path[w] = v; } } } } /* 输出最短路径 */ for(int vi = 0; vi < N; ++ vi){ cout << G.vertex[vi]; if(S[vi]){ for(int vj = Path[vi]; vj != -1; vj = Path[vj]){ cout << "←" << G.vertex[vj]; } cout << " (" << D[vi] << ")" << endl; }else{ cout << " (INF)" << endl; } } }

代码中的图为：

运行结果：

---

每一对顶点之间的最短路径

弗洛伊德算法

Floyd算法（Floyd-Warshall algorithm）又称为弗洛伊德算法、插点法，是解决给定的加权图中顶点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

算法步骤如下：

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是更新它。

把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

完整C++代码：

#include <iostream> #include <climits> #include <iomanip> using namespace std; #define MAX_VERTEX_NUM 20 // 顶点数量上限 typedef char VerType; // 顶点结构 , 顶点的字母名称 typedef int ArcType; // 边的结构 , 权值 typedef enum {DG, UDG} GKind; // 图类型，{有向图,无向图} // 图的存储结构 typedef struct { int verNum, arcNum; // 顶点数量, 边数量 GKind kind; // 图类型 VerType vertex[MAX_VERTEX_NUM]; //顶点 ArcType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //边 }Graph; void CreateGraphByArray(Graph &G); // 创建图G (通过预定义的数组) int VertexLoc(const Graph &G, const VerType &v); // 获取顶点v在图G中的位置 void ShortestPath_Floyd(Graph &G); // 最短路径算法 (弗洛伊德算法) int main() { Graph G; CreateGraphByArray(G); ShortestPath_Floyd(G); return 0; } void CreateGraphByArray(Graph &G) { G.kind = DG; const int vn = 4; VerType V[vn + 1] = {"0123"}; const int en = 8; VerType V1[en + 1] = {"00112223"}; VerType V2[en + 1] = {"13323012"}; ArcType E[en] = {1,4,2,9,8,3,5,6}; // 输入顶点 G.verNum = vn; for(int i = 0; i < G.verNum; ++ i){ G.vertex[i] = V[i]; } // 初始化邻接矩阵 for(int vi = 0; vi < G.verNum; ++ vi){ for(int vj = 0; vj < G.verNum; ++ vj){ G.arcs[vi][vj] = INT_MAX; } } // 输入边 G.arcNum = en; for(int i = 0; i < G.arcNum; ++ i){ VerType &v1 = V1[i], &v2 = V2[i]; ArcType &e = E[i]; int vi = VertexLoc(G, v1), vj = VertexLoc(G, v2); if(vi == G.verNum || vj == G.verNum){ continue; } if(UDG == G.kind){ G.arcs[vi][vj] = G.arcs[vj][vi] = e; }else{ G.arcs[vi][vj] = e; } } } int VertexLoc(const Graph &G, const VerType &v) { for(int i = 0; i < G.verNum; ++ i){ if(G.vertex[i] == v){ return i; } } return G.verNum; } void ShortestPath_Floyd(Graph &G) { const int N = G.verNum; int Path[N][N]; //表示vi和vj之间的最短路上的前驱顶点 long long D[N][N]; //表示vi和vj之间的最短路径长度 for(int i = 0; i < N ; ++ i){ for(int j = 0; j < N; ++ j){ D[i][j] = G.arcs[i][j]; Path[i][j] = D[i][j] != INT_MAX ? i : -1; } } for(int k = 0; k < N; ++ k){ for(int i = 0; i < N; ++ i){ for(int j = 0; j < N; ++ j){ if(D[i][k] + D[k][j] < D[i][j]){ D[i][j] = D[i][k] + D[k][j]; Path[i][j] = Path[k][j]; } } } } /* 输出每对最短路径 */ for(int i = 0; i < N; ++ i){ for(int j = 0; j < N; ++ j){ cout << G.vertex[i] << "→" << G.vertex[j] << ": " << G.vertex[j]; for(int vi = Path[i][j]; vi != i; vi = Path[i][vi]){ cout << "←" << G.vertex[vi]; } cout << "←" << G.vertex[i] << " (" << D[i][j] << ")" << endl; } } }

对于下面的图：

运行结果：