最短路径 之 dijkstra算法.ppt

最短路径求法
之
Dijkstra算法的理解
YOSO

Shenzhen University
Dijkstra算法过程:
1、先根据带权图建立一个邻接矩阵,如下面的图:
0
1
2
4
3
10
50
20
10
60
100
30
建立的邻接矩阵为:
变为计算机能
识别的二维数组
graph[5][5] ={
{0, 10, MAXVALUE, 30, 100},
{MAXVALUE, 0, 50, MAXVALUE, MAXVALUE},
{MAXVALUE, MAXVALUE, 0, MAXVALUE, 10},
{MAXVALUE, MAXVALUE, 20, 0, 60},
{MAXVALUE, MAXVALUE, MAXVALUE, MAXVALUE, 0}
};
因为计算机无法表示∞的数,所以这里的∞用一个自定义的最大值MAXVALUE来表示,那么MAXVALUE要取多大呢?因为2^31 = 2147483648, 所以MAXVALUE可取2100000000。取其它值也可以,只要保证MAXVALUE+图中的某个最大的权值后,MAXVALUE不会变为负(溢出,你懂的^ ^)
①建立一个表示当前已知顶点0到其它顶点最短距离的数组,如distance[5]。
②建立一个标记两顶点最短距离是否已经找到的数组,例如为found[5],
设found[i](i: 0→4)为TRUE表示顶点0到顶点i的最短距离已经找到,
为FALSE则表示未找到。
③(可要可不要)建立一个标记最短路径间经过的顶点的数组,例如为path[5][5],
设path[i][j]为TRUE时表示从0到顶点i的最短路径中经过j顶点。
有了graph[5][5]二维数组后,我们就可以根据它来求各顶点间的最短路径啦,
这里我们假设我们要求的是从顶点0到其它顶点的最短路径。
2、建立求解最短路径时需要用到的数组:
0
1
2
4
3
10
50
20
10
60
100
30
0
1
2
4
3
10
50
20
10
60
100
30
3、初始化各个数组:
① for(i=0; i<5; i++){distance[i] = graph[0][i];}
② for(i=0; i<5; i++){found[i] = FALSE;} //假设已先宏定义FALSE,如#define FALSE 0
③ for(i=0; i<5; i++)
{
for(j=0; j<5; j++)
path[i][j] = FALSE;

if(distance[i] < MAXVALUE)
{
path[i][0] = TRUE;
path[i][i] = TRUE;
} //这个初始化的意思是刚开始的时候,如果顶点0到顶点i有直接的路径,我们标记从
} //顶点0到顶点i有经过顶点0和顶点i。可能你会想,从顶点0到顶点i的最短路径显然
//是有经过顶点0和顶点i的嘛,但是当i点是孤立一个点,即没有路径能达到i点的时候呢?
有了上面的准备后,我们就可以开始求顶点0到其它顶点的最短路径啦~
0
1
2
4
3
10
50