一.最短路径
- 从某顶点(源点)出发到另一顶点(目的地)的路径中,有一条各边(或弧)权值之和最小的路径称为最短路径
- 迪杰斯特拉算法:从单原点到其余各店的最短路径
二.基本思想
依最短路径的长度递增的次序求得各条路径。其中,从源点到顶点v的最短路径是所有最短路径中长度最短者
- 路径长度最短的最短路径的特点:
在这条路上,必定只含一条弧,并且这条弧的权值最小(记为v0->v1)
- 下一条路径长度次短的最短路径的特点:
或者是直接从源点到该点(只含一条弧)
或者是从源点经过顶点v1,再到达该顶点(由两条弧组成)(v0->v1->v2)
- 再下一条路径长度次短的的最短路径的特点:
或者是直接从源点到该点(只含一条弧)
或者是从源点经过顶点v1,再到达该顶点(由两条弧)
或者是从源点经过顶点v2,再到达该顶点(看v2的情况,第一种就两条弧,第二种就三条弧)
- 重复步骤
三.步骤图解
步骤:
S中存放的是已经求得的最短路径的终点的集合,v-s集合包含其他点
i代表第i条最短路径(及可能路径走法)
邻接矩阵表示弧<vi,vj>上的权值
dist[i]值
若vi在S中,dist[i]表示源点到vi的最短路径长度
若vi在V-S中,dist[i]表示源点到vi的只包括S中的顶点为中间顶点的最短路径
- 找路径长度最短的最短路径,首先看从0开始弧度为1的点,列出即为v0->v2,v0->v4,v0->v5.以及它们的权值(即表格第一列)在第一列中找出第一条最短路径是v0->v2权值为10,画上对号。那么此时v0到v2的最短路径就找到了,v2一行可以省略了
- 继续以v2为顶点查找下一步可行路线,由邻接矩阵或者直接看图找,可得v0->v2->v3将此路线及它的权值与之前找到的最短路径(第一列剩下的路径)做比较,即从V-S中找出路径最短的顶点(即为v4),并将其加入到S中;接着,更新V-S中的顶点和顶点对应的路径(即第三步以v4为顶点查找)。
- 以v4为顶点查找下一步,与上相同,从V-S中找出路径,相互比较,找出最小的(v3),并将其加入到S中;接着,更新V-S中的顶点和顶点对应的路径。
- 重复步骤,最终完成,找出来每次的最短路径,将所有可以到达的点都包含在S中。
四.代码说明
/*
* Dijkstra最短路径。
* 即,统计图(G)中"顶点vs"到其它各个顶点的最短路径。
*
* 参数说明:
* G -- 图
* vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
* prev -- 前驱顶点数组。即,prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中,位于"顶点i"之前的那个顶点。
* dist -- 长度数组。即,dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
*/
void dijkstra(Graph G, int vs, int prev[], int dist[])
{
int i,j,k;
int min;
int tmp;
int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
// 初始化
for (i = 0; i < G.vexnum; i++)
{
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
}
// 对"顶点vs"自身进行初始化
flag[vs] = 1;
dist[vs] = 0;
// 遍历G.vexnum-1次;每次找出一个顶点的最短路径。
for (i = 1; i < G.vexnum; i++)
{
// 寻找当前最小的路径;
// 即,在未获取最短路径的顶点中,找到离vs最近的顶点(k)。
min = INF;
for (j = 0; j < G.vexnum; j++)
{
if (flag[j]==0 && dist[j]<min)
{
min = dist[j];
k = j;
}
}
// 标记"顶点k"为已经获取到最短路径
flag[k] = 1;
// 修正当前最短路径和前驱顶点
// 即,当已经"顶点k的最短路径"之后,更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (j = 0; j < G.vexnum; j++)
{
tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出
if (flag[j] == 0 && (tmp < dist[j]) )
{
dist[j] = tmp;
prev[j] = k;
}
}
}
// 打印dijkstra最短路径的结果
printf("dijkstra(%c): \n", G.vexs[vs]);
for (i = 0; i < G.vexnum; i++)
printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);
}
参考文章
文章中附有迪杰斯特拉(Dijkstra)算法源码