最短路径算法

Dijkstra算法:

基本思想是:每次找到离源点最近的一个点,然后以改点为中心扩展,最终得到源点到其余所有点的最短路径。

基本步骤:

1、将所有的顶点分为两部分,一部分是已知最短路程的顶点集合P,另一部分是未知最短路程的顶点集合Q。最开始时,第一部分P只有源点一个顶点,我们可以使用book数组标记哪些点在第一不部分中。book[i]=1 就表示这个顶点i在集合P中。

2、设置源点s到自己的最短路径为0,即dis[s]=0,若存在有源点能够直接到达的顶点i,则把dis[i]设为e[s][i],同时把其他不能直接到源点的顶点的点距离设置为正无穷。

3、在集合Q中选择一个离源点路程最近的顶点u,即dis[u]最小,加入到集合P中,并考察所有顶点u能够到达的点的路程值是否需要更新。如存在一条从u到v的边,那么可以通过将边u》v添加到尾部来拓展一条从s到v的路径,这条路径的长度为dis[u]+e[u][v].如果这个值dis[u]+e[u][v].比目前已知的dis[v]的值要小,我们则更新dis[v]的值为dis[u]+e[u][v]。

4、重复3,直到Q集合为空。算法结束。

 

其核心部分代码如下:

//存在有源点能够直接到达的顶点i,则把dis[i]设为e[s][i],同时把其他不能直接到源点的顶点的点距离设置为正无穷
for(i = 1; i <= n; i++)
    dis[i]=e[1][i];

//最开始时,第一部分P只有源点一个顶点
for(i = 1; i <= n; i++)
    book[i] = 0;
book[1] = 1;

//Dijkstra算法核心语句
for(i = 1; i<=n-1; i++)    //还需要往P集中中添加n-1个顶点
{
    //找到离源点最近的顶点
    min = 999999;
    for(j = 1; j <= n; j++)
    {
        if(book[j] == 0 && dis[j] < min)
        {
            min = dis[j];
            u = j;
        }
    }

    book[u] = 1;
    for(v=1; v<=n; v++)
    {
        if(e[u][v] < 999999 && dis[v] > dis[u]+e[u][v])
            dis[v] = dis[u]+e[u][v];
    }
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。