单源点的最短路径：给定带权有向图G和源点v，求从源点v到G中其余各顶点的最短路径。
Dijkstra提出一个按路径长度递增的次序产生最短路径的算法。
算法描述：
1）S为已找到从v出发的最短路径终点的集合，它的初始状态为空寂。那么从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为：
D[i] = arcs[Locate Vex(G,v)][i]
2）选择vj，使得D[j] = Min{D[i]}
vj就是当前求得的一条从v出发的最短路径的终点。S= SU{j}。
3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。
4）重复上述操作，求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。
dist记录从源点到其他各顶点当前的最短距离，其初值为diat[i]=cost[v][i],从S之外的顶点集合V-S中选出一个顶点Vu，使得dist[u]的值最小。
于是从源点到达Vu只通过s中的顶点，把u加入集合s中调整dist中的记录从源点到V-S中每个顶点Vj的距离：
从原来的dist[j]和dist[u]+cost[u][j]中选择较小的值作为新的dist[j].
path用于保存最短路径长度。path[i]保存从源点v到终点Vi当前最短路径中的前一个顶点的编号，它的初值为源点v的编号或-1(表示无边)。
算法实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131#include <stdio.h>
#include<stdlib.h>
//图的邻接矩阵表示方法
#define INF INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum{ DG, DN, UDG, UDN } GraphKind;
typedef int VRType;
typedef int InfoType;
typedef int VertexType;
typedef struct{
VRType adj; //VRType是顶点关系类型，对无权图 用1 或 0 表示相邻否
//对于带权图，则为权值类型
InfoType *info;
}ArcCell, AdjMaxtrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];
AdjMaxtrix arcs;
int vexnum, arcnum;
GraphKind kind;
}MGraph;
int graph[6][6] = {
INF, INF, 10, INF, 30, 100,
INF, INF, 5, INF, INF, INF,
INF, INF, INF, 50, INF, INF,
INF, INF, INF, INF, INF, 10,
INF, INF, INF, 20, INF, 60,
INF, INF, INF, INF, INF, INF
};
int createDG(MGraph &M){
M.vexnum = 6;
M.arcnum = 10;
//顶点的信息
for (int i = 0; i < M.vexnum; i++){
M.vexs[i] = i + 1;
}
//边的权重等信息
for (int i = 0; i < M.vexnum; i++){
for (int j = 0; j < M.vexnum; j++){
M.arcs[i][j].adj = graph[i][j];
}
}
return 1;
}
void DisplayMatix(MGraph &G){
for (int i = 0; i < G.vexnum; i++){
for (int j = 0; j < G.vexnum; j++){
if (G.arcs[i][j].adj == INF){
printf("oo ");
}
else{
printf("%d ", G.arcs[i][j].adj);
}
}
printf("\n");
}
}
int dist[6];//dist记录从源点到其他各顶点当前的最短距离，
int path[6];//path用于保存最短路径长度。path[i]保存从源点v到终点Vi当前最短路径中的前一个顶点的编号，它的初值为源点v的编号或-1(表示无边)。
int final[MAX_VERTEX_NUM];//是否找到最短路径
void ShortestPath_DIJ(MGraph G, int v0){
int min,v;
for ( v = 0; v < G.vexnum; ++v){
final[v] = false;
dist[v] = G.arcs[v0][v].adj;
if (G.arcs[v0][v].adj == INF){
path[v] = -1;
}
else{
path[v] = v0;
}
}
path[v0] = 0;
final[v0] = true;
for (int i = 1; i < G.vexnum; ++i){
min = INF;
for (int w = 0; w < G.vexnum; ++w){
if (!final[w])
if (dist[w] < min){
v = w;
min = dist[w];
}
}
if (v != -1){
final[v] = true;
for (int w = 0; w < G.vexnum; ++w){
if (!final[w] && G.arcs[v][w].adj < INF && (min + G.arcs[v][w].adj < dist[w])){
dist[w] = min + G.arcs[v][w].adj;
path[w] = v;
}
}
}
}
int pre;
printf("Dijkstra算法求解如下：\n");
for (int i = 0; i < G.vexnum;i++){
if (i != v0){
printf("v%d -> v%d:", v0, i);
if (final[i] == true){
printf("%d ",dist[i]);
pre = i;
printf("逆序输出 : ");
while (pre != v0){
printf("%d,", pre);
pre = path[pre];
}
printf("%d\n",pre);
}
else{
printf("不存在\n");
}
}
}
}
int main(){
MGraph G;
createDG(G);
DisplayMatix(G);
ShortestPath_DIJ(G, 0);
return 0;
}