迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，基于贪心策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
算法思路
Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v0放入S，集合S每并入一个新顶点vi，都要修改源点v0到集合V-S中顶点当前的最短路径长度值。
本例基于邻接矩阵存储的图。
在构造的过程中要设置三个辅助数组：
-
flag[]：用以表示是否已找到从源点v0到其他各顶点当前的最短路径长度。 -
dist[]：记录从源点v0到其他各顶点当前的最短路径长度，它的初态为：若从v0到vi有弧，则dist[i]为弧上的权值；否则置dist[i]为∞。 -
path[]：path[i]表示从源点到顶点i之间的最短路径的前驱节点。在算法结束时，可根据其值追溯到源点v0到顶点vi的最短路径。
假设从顶点0出发，即v0=0，集合S最初只包含顶点0，邻接矩阵edge[][]表示带权有向图，edge[i][j]表示有向边<i,j>的权值，若不存在有向边<i,j>，则edge[i][j]为∞。
算法步骤
Dijkstra算法的步骤如下：
- 初始化：集合S初始为{0}，
dist[]的初值dist[i] = edge[0][i]，i=1,2,···,n-1。path[0]设为“-”，表示无。 - 从顶点集合V-S中选出vj，满足
dist[j] = min {dist[i] | vi∈V-S}，vj就是当前求得的一条从v0出发的最短路径的终点，令S=S ∪ { j }，并使flag[j]设为true。 - 修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：若
dist[k] > dist[j] + edge[j][k]，则更新dist[k] = dist[j] + edge[j][k]，同时更新path[k] = vj。 - 重复【步骤2~3】共n-1次，直到所有的顶点都包含在S中。
注意：Dijkstra算法并不适用于图边上带有负权值时的情况
完整代码
#include <stdio.h>
#define MaxVertexNum 100 // 顶点数目最大值
#define INFINITY 65535 // ∞
#define true 1
#define false 0
typedef int bool;
typedef char VertexType; // 顶点的数据类型
typedef int EdgeType; // 带权图中边上权值的数据类型
typedef struct {
VertexType vex[MaxVertexNum]; // 顶点表
EdgeType edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵，边表
int vexNum, arcNum; // 图的当前顶点数和弧数
} MGraph;
// 打印图的信息
void printGraph(MGraph g);
// 迪杰斯特拉算法
void dijkstra(MGraph graph);
int main() {
MGraph g;
g.arcNum = 0;
g.vexNum = 0;
printf("请输入顶点个数：");
scanf("%d", &g.vexNum);
printf("请输入%d个顶点编号：\n", g.vexNum);
for (int i = 0; i < g.vexNum; i++) {
scanf("%c", &g.vex[i]);
// 过滤回车及空格
while (g.vex[i] == '\r' || g.vex[i] == '\n' || g.vex[i] == ' ') {
scanf("%c", &g.vex[i]);
}
}
printf("请输入该图的邻接矩阵：\n");
for (int i = 0; i < g.vexNum; ++i) {
for (int j = 0; j < g.vexNum; ++j) {
scanf("%d", &g.edge[i][j]);
if (g.edge[i][j] > 0) {
g.arcNum++;
}
if (g.edge[i][j] == -1) {
g.edge[i][j] = INFINITY;
}
}
}
printGraph(g);
dijkstra(g);
return 0;
}
void dijkstra(MGraph graph) {
bool flag[graph.vexNum]; // 是否已找到最短路径
int dist[graph.vexNum]; // 最短路径长度
VertexType path[graph.vexNum]; // 前驱节点
int min, index; // min -- 临时记录未找到最短路径的节点中的最短路径长度，index -- 下标
for (int i = 0; i < graph.vexNum; ++i) { // 初始化
flag[i] = false;
dist[i] = INFINITY;
path[i] = graph.vex[0];
}
flag[0] = true;
for (int i = 0; i < graph.vexNum; ++i) { // 对V0节点进行初始化
dist[i] = graph.edge[0][i];
if (dist[i] != INFINITY) {
path[i] = graph.vex[0];
}
}
path[0] = '-';
for (int i = 1; i < graph.vexNum; ++i) { // 循环n-1次，找出其余最短路径
min = INFINITY;
for (int j = 0; j < graph.vexNum; ++j) { // 节点Vi到其他节点的路径
if (flag[j] == false && min > dist[j]) { // 找出最短距离，记录其下标
min = dist[j];
index = j;
}
}
flag[index] = true; // 标记为已找到最短路径
for (int k = 0; k < graph.vexNum; ++k) { // 更新最短距离及前驱节点
if (flag[k] == false && dist[k] > dist[index] + graph.edge[index][k]) {
dist[k] = dist[index] + graph.edge[index][k];
path[k] = graph.vex[index];
}
}
}
// ----------打印信息---------------
printf("\t顶点");
for (int i = 0; i < graph.vexNum; ++i) {
printf("\t%c", graph.vex[i]);
}
printf("\n");
printf("\tflag");
for (int i = 0; i < graph.vexNum; ++i) {
printf("\t%s", flag[i] == true ? "true" : "false");
}
printf("\n");
printf("\tdist");
for (int i = 0; i < graph.vexNum; ++i) {
printf("\t%d", dist[i]);
}
printf("\n");
printf("\tpath");
for (int i = 0; i < graph.vexNum; ++i) {
printf("\t%c", path[i]);
}
printf("\n");
// --------------------------------
}
// 打印图的信息
void printGraph(MGraph g) {
printf("顶点数：%d，弧数：%d\n", g.vexNum, g.arcNum);
printf("顶点编号：\n");
for (int i = 0; i < g.vexNum; ++i) {
printf("\t%c", g.vex[i]);
}
printf("\n");
printf("邻接矩阵：\n");
for (int i = 0; i < g.vexNum; ++i) {
for (int j = 0; j < g.vexNum; ++j) {
if (g.edge[i][j] != INFINITY) {
printf("\t%d", g.edge[i][j]);
} else {
printf("\t∞");
}
}
printf("\n");
}
}
测试数据
顶点数：5，弧数：10
顶点编号：A B C D E
邻接矩阵：
0 10 -1 -1 5
-1 0 1 -1 2
-1 -1 0 4 -1
7 -1 6 0 -1
-1 3 9 2 0
参考结果：
顶点 A B C D E
flag true true true true true
dist 0 8 9 7 5
path - E B E A
网友评论