知识点
单源最短路径：Dijkstra
Dikstra算法也用来解决单源最短路径问题。Dijkstra是非常高效而且稳定的算法。
Bellman-Ford算法，提到它在现实中的模型是找警察问路。在现实中 Dijkstra有另外的模型，例如多米诺骨牌，可以想象下面的场景：
在图中所有的边上排满多米诺骨牌，相当于把骨牌看成图的边。一条边上的多米诺骨牌数量和边的权值(例如长度或费用)成正比，规定所有骨牌倒下的速度都是一样的。如果在一个结点上推倒骨牌，会导致这个结点上的所有骨牌都往后面倒下去。
在起点 s s s 推倒骨牌，可以观察到，从 s s s 开始。它连接的边上的骨牌都逐渐倒下，并到达所有能达到的结点。在某个结点 t t t ，可能先后从不同的线路倒骨牌过来；先倒过来的骨牌，其经过的路径肯定就是从 s s s 到达 t t t 的最短路径；后倒过来的骨牌，对确定结点 t t t 的最短路径没有贡献,不用管它。
从整体看,这就是一个从起点;扩散到整个图的过程。在这个过程中观察所有结点的最短路径是这样得到的:
- 在 s s s 的所有直连邻居中，最近的邻居 u u u ，骨牌首先到达。 u u u 是第一个确定最短路径的结点。从 u u u 直连到 s s s 的路径肯定是最短的,因为如果 u u u 绕道别的结点到 s s s ，必然更远。
- 然后，把后面骨牌的倒下分成两个部分，一部分是从 s s s 继续例下到 s s s 的其他的直连邻居，另一部分是从 u u u 出发倒下到 u u u 的直连邻居。那么下一个到达的结点 v v v 必然是 s s s 或者 u u u 的一个直连邻居。 v v v 是第二个确定最短路径的结点。
- 继续以上步骤，在每一次迭代过程中都能确定一个结点的最短路径。
Dijkstra算法应用了贪心法的思想，即“抄近路走"，肯定能找到最短路径。
在上述步骤中可以发现：Dijkstra的每次选代，只需要检查上次已经确定最短路径的那些结点的邻居，检查范围很小，算法是高效的；每次迭代，都能得到至少一个结点的最短路径，算法是稳定的。
与Bellman Ford 对比:
Bellman-Ford 是分布式的思想;面 Dijkstra必须从起点s开始扩散和计算，是集中式的思想。读者可以试试在多米诺骨牌模型中运用Bellman-Ford,看看行不行。
算法实现
//算法7.15
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D){
/* 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度 D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径 算法7.15 */
int v, w, i, j, min;
Status final[MAX_VERTEX_NUM];
for (v = 0; v < G.vexnum; ++v){
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w = 0; w < G.vexnum; ++w)
P[v][w] = FALSE;
if (D[v] < INFINITY){
P[v][v0] = TRUE;
P[v][v] = TRUE;
}
}
D[v0] = 0;
final[v0] = TRUE; // 初始化,v0顶点属于S集
for (i = 1; i < G.vexnum; ++i) //其余G.vexnum-1个顶点
{
// 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集
min = INFINITY; // 当前所知离v0顶点的最近距离
for (w = 0; w < G.vexnum; ++w)
if (!final[w]) // w顶点在V-S中
if (D[w] < min){
v = w;
min = D[w];
} //w顶点离v0顶点更近
final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w = 0; w < G.vexnum; ++w) {
// 更新当前最短路径及距离
if (!final[w] && min < INFINITY&&G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w])){
D[w] = min + G.arcs[v][w].adj;
for (j = 0; j < G.vexnum; ++j)
P[w][j] = P[v][j];
P[w][w] = TRUE;
}
}
}
}
完整代码
#include<bits/stdc++.h>
using namespace std;
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int Boolean;
#define MAX_NAME 5
#define MAX_INFO 20
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
/* ------------------ 图的数组(邻接矩阵)存储表示 ----------------*/
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum {
DG, DN, AG, AN }GraphKind;
typedef struct{
VRType adj;
InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
GraphKind kind;
}MGraph;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
/* ----------- 需要用的图的数组(邻接矩阵)存储的基本操作 -----------*/
int LocateVex(MGraph G, VertexType u){
/* 初始条件:图G存在,u和G中顶点有相同特征 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for (i = 0; i < G.vexnum; ++i)
if (strcmp(u, G.vexs[i]) == 0)
return i;
return -1;
}
Status CreateDN(MGraph &G){
int i, j, k, w, IncInfo;
char s[MAX_INFO], *info;
VertexType va, vb;
printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)(以空格作为间隔): ");
scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n", G.vexnum, MAX_NAME);
for (i = 0; i < G.vexnum; ++i)
scanf("%s", G.vexs[i]);
for (i = 0; i < G.vexnum; ++i)
for (j = 0; j < G.vexnum; ++j){
G.arcs[i][j].adj = INFINITY;
G.arcs[i][j].info = NULL;
}
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n", G.arcnum);
for (k = 0; k < G.arcnum; ++k){
scanf("%s%s%d%*c", va, vb, &w);
i = LocateVex(G, va);
j = LocateVex(G, vb);
G.arcs[i][j].adj = w;
if (IncInfo){
printf("请输入该弧的相关信息(<%d个字符): ", MAX_INFO);
gets(s);
w = strlen(s);
if (w){
info = (char*)malloc((w + 1) * sizeof(char));
strcpy(info, s);
G.arcs[i][j].info = info;
}
}
}
G.kind = DN;
return OK;
}
//算法7.15
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D){
/* 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度 D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径 算法7.15 */
int v, w, i, j, min;
Status final[MAX_VERTEX_NUM];
for (v = 0; v < G.vexnum; ++v){
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w = 0; w < G.vexnum; ++w)
P[v][w] = FALSE;
if (D[v] < INFINITY){
P[v][v0] = TRUE;
P[v][v] = TRUE;
}
}
D[v0] = 0;
final[v0] = TRUE; // 初始化,v0顶点属于S集
for (i = 1; i < G.vexnum; ++i) //其余G.vexnum-1个顶点
{
// 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集
min = INFINITY; // 当前所知离v0顶点的最近距离
for (w = 0; w < G.vexnum; ++w)
if (!final[w]) // w顶点在V-S中
if (D[w] < min){
v = w;
min = D[w];
} //w顶点离v0顶点更近
final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w = 0; w < G.vexnum; ++w) {
// 更新当前最短路径及距离
if (!final[w] && min < INFINITY&&G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w])){
D[w] = min + G.arcs[v][w].adj;
for (j = 0; j < G.vexnum; ++j)
P[w][j] = P[v][j];
P[w][w] = TRUE;
}
}
}
}
int main(){
int i, j, v0 = 0;
MGraph g;
PathMatrix p;
ShortPathTable d;
CreateDN(g);
ShortestPath_DIJ(g, v0, p, d);
printf("最短路径数组 PathMatrix[i][j] 如下:\n");
for (i = 0; i < g.vexnum; ++i){
for (j = 0; j < g.vexnum; ++j)
printf("%2d", p[i][j]);
printf("\n");
}
printf("%s到各顶点的最短路径长度为：\n", g.vexs[0]);
for (i = 1; i < g.vexnum; ++i)
printf("%s-%s:%d\n", g.vexs[0], g.vexs[i], d[i]);
return 0;
}
测试样例
请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)(以空格作为间隔): 6 8 0
请输入6个顶点的值(<5个字符):
v0 v1 v2 v3 v4 v5
请输入8条弧的弧尾 弧头 权值(以空格作为间隔):
v0 v5 100
v0 v4 30
v0 v2 10
v1 v2 5
v2 v3 50
v3 v5 10
v4 v3 20
v4 v5 60
运行结果
最短路径数组 PathMatrix[i][j] 如下:
0 0 0 0 0 0
0 0 0 0 0 0
1 0 1 0 0 0
1 0 0 1 1 0
1 0 0 0 1 0
1 0 0 1 1 1
v0到各顶点的最短路径长度为：
v0-v1:2147483647
v0-v2:10
v0-v3:50
v0-v4:30
v0-v5:60
京公网安备 11010502036488号