Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,比如数据结构、图论、运筹学等。
1、算法思想
令G = (V,E)为一个带权有向图,把图中的顶点集合V分成两组,第一组为已求出最短路径的顶点集合S(初始时S中只有源节点,以后每求得一条最短路径,就将它对应的顶点加入到集合S中,直到全部顶点都加入到S中);第二组是未确定最短路径的顶点集合U。在加入过程中,总保持从源节点v到S中各顶点的最短路径长度不大于从源节点v到U中任何顶点的最短路径长度。
2、算法步骤
(1)初始化时,S只含有源节点;
(2)从U中选取一个距离v最小的顶点k加入S中(该选定的距离就是v到k的最短路径长度);
(3)以k为新考虑的中间点,修改U中各顶点的距离;若从源节点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值是顶点k的距离加上k到u的距离;
(4)重复步骤(2)和(3),直到所有顶点都包含在S中。
具体图例与算法执行步骤:(就从A开始,到各节点的最短路径)。
![](http://blog.chinaunix.net/attachment/201308/5/26548237_1375690988g83C.png)
具体执行步骤如下图所示。
![](http://blog.chinaunix.net/attachment/201308/5/26548237_13756910383KwB.png)
![](http://blog.chinaunix.net/attachment/201308/5/26548237_13756910383KwB.png)
PS:图片右下角是原作者的博客地址。
3、算法具体实现
算法的具体实现如下所示。
3、算法具体实现
算法的具体实现如下所示。
-
#include "stdio.h"
-
#include "stdlib.h"
-
#include "io.h"
-
#include "math.h"
-
#include "time.h"
-
-
#define OK 1
-
#define ERROR 0
-
#define TRUE 1
-
#define FALSE 0
-
-
#define MAXEDgE 20
-
#define MAXVEX 20
-
#define INFINITY 65535
-
-
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
-
-
-
typedef struct
-
{
-
int vexs[MAXVEX];
-
int arc[MAXVEX][MAXVEX];
-
int numVertexes, numEdges;
-
}Mgraph;
-
-
typedef int Patharc[MAXVEX]; /* 用于存储最短路径下标的数组 */
-
typedef int ShortPathTable[MAXVEX]; /* 用于存储到各点最短路径的权值和 */
-
-
-
void CreateMgraph(Mgraph *g)
-
{
-
int i, j;
-
-
/* printf("请输入边数和顶点数:"); */
-
g->numEdges=16;
-
g->numVertexes=9;
-
-
for (i = 0; i < g->numVertexes; i++)/* 初始化图 */
-
{
-
g->vexs[i]=i;
-
}
-
-
for (i = 0; i < g->numVertexes; i++)/* 初始化图 */
-
{
-
for ( j = 0; j < g->numVertexes; j++)
-
{
-
if (i==j)
-
g->arc[i][j]=0;
-
else
-
g->arc[i][j] = g->arc[j][i] = INFINITY;
-
}
-
}
-
-
g->arc[0][1]=1;
-
g->arc[0][2]=5;
-
g->arc[1][2]=3;
-
g->arc[1][3]=7;
-
g->arc[1][4]=5;
-
-
g->arc[2][4]=1;
-
g->arc[2][5]=7;
-
g->arc[3][4]=2;
-
g->arc[3][6]=3;
-
g->arc[4][5]=3;
-
-
g->arc[4][6]=6;
-
g->arc[4][7]=9;
-
g->arc[5][7]=5;
-
g->arc[6][7]=2;
-
g->arc[6][8]=7;
-
-
g->arc[7][8]=4;
-
-
-
for(i = 0; i < g->numVertexes; i++)
-
{
-
for(j = i; j < g->numVertexes; j++)
-
{
-
g->arc[j][i] =g->arc[i][j];
-
}
-
}
-
-
}
-
-
/* Dijkstra算法,求有向网g的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */
-
/* P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */
-
void ShortestPath_Dijkstra(Mgraph g, int v0, Patharc *P, ShortPathTable *D)
-
{
-
int v,w,k,min;
-
int final[MAXVEX]; /* final[w]=1表示求得顶点v0至vw的最短路径 */
-
-
/* 初始化数据 */
-
for(v=0; v<g.numVertexes; v++)
-
{
-
final[v] = 0; /* 全部顶点初始化为未知最短路径状态 */
-
(*D)[v] = g.arc[v0][v]; /* 将与v0点有连线的顶点加上权值 */
-
(*P)[v] = 0; /* 初始化路径数组P为0 */
-
}
-
-
(*D)[v0] = 0; /* v0至v0路径为0 */
-
final[v0] = 1; /* v0至v0不需要求路径 */
-
-
/* 开始主循环,每次求得v0到某个v顶点的最短路径 */
-
for(v=1; v<g.numVertexes; v++)
-
{
-
min=INFINITY; /* 当前所知离v0顶点的最近距离 */
-
for(w=0; w<g.numVertexes; w++) /* 寻找离v0最近的顶点 */
-
{
-
if(!final[w] && (*D)[w]<min)
-
{
-
k=w;
-
min = (*D)[w]; /* w顶点离v0顶点更近 */
-
}
-
}
-
final[k] = 1; /* 将目前找到的最近的顶点置为1 */
-
-
/* 修正当前最短路径及距离 */
-
for(w=0; w<g.numVertexes; w++)
-
{
-
/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
-
if(!final[w] && (min+g.arc[k][w]<(*D)[w]))
-
{
-
/* 说明找到了更短的路径,修改D[w]和P[w] */
-
(*D)[w] = min + g.arc[k][w]; /* 修改当前路径长度 */
-
(*P)[w]=k;
-
}
-
}
-
}
-
}
-
-
int main(void)
-
{
-
int i,j,v0;
-
Mgraph g;
-
Patharc P;
-
ShortPathTable D; /* 求某点到其余各点的最短路径 */
-
v0=0;
-
-
CreateMgraph(&g);
-
-
ShortestPath_Dijkstra(g, v0, &P, &D);
-
-
printf("最短路径倒序如下:\n");
-
for(i=1;i<g.numVertexes;++i)
-
{
-
printf("v%d - v%d : ",v0,i);
-
j=i;
-
while(P[j]!=0)
-
{
-
printf("%d ",P[j]);
-
j=P[j];
-
}
-
printf("\n");
-
}
-
printf("\n源点到各顶点的最短路径长度为:\n");
-
for(i=1;i<g.numVertexes;++i)
-
printf("v%d - v%d : %d \n",g.vexs[0],g.vexs[i],D[i]);
-
return 0;
- }