单源最短路径Dijkstra算法

Dijkstra算法简述

　　Dijkstra算法是图论中的一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：集合T包含所有当前已经找到最短路径的点，初始情况下T中只有源点，U = V – T，其中V为图G的点集。从源点开始，每次新扩展一个属于U、距离T中点最短的点，用该点更新U中的与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。若要处理含有负权值边的情况，就需要使用Bellman-Ford算法了。

Dijkstra算法流程

　　在以下说明中，start为源，Adj[u,v]为点u和v之间的边的长度，结果保存在Closest[]

  • 初始化：源的距离Closest[start]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
  • 以下过程循环n-1次：
    在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
    对于每个与u相邻的点v，如果Closest[u]+Adj[u,v] < Closest[v]，那么把Closest[v]更新成更短的距离Closest[u]+Adj[u,v]。此时到点v的最短路径上，前一个节点即为u。
  • 结束。此时对于任意的u，Closest[u]就是start到u的距离。

Dijkstra算法C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int MAXINT = 0xFFFF; //~ 不可达的路径长度上限
class Node
{
public:
    Node(): w(MAXINT), v(false){}
    int src, //~ 最短路径上的上一个顶点
        w; //~ 到该节点的路径长度
    bool v; //~ 标识该节点是否已经加入最短路径集
};
int
main(int argc, char **argv)
{
    vector<vector<int> > Adj;
    int n, // 顶点数
        m, //~ 边数
        from,
        to,
        w,
        min = MAXINT,
        start, //~ 源点
        k; //~ 下一个可以加入的顶点号
    cin>>n;
    vector<Node> Closest(n);
    for(int i = 0; i < n; ++i)
    {
        Adj.push_back(vector<int>(n, MAXINT));
        Adj[i][i] = 0;
    }
    cin>>m;
    for(int i = 0; i < m; ++i)
    {
        cin>>from>>to>>w;
        Adj[from][to] = w;
    }
    cin>>start; //~ 从顶点start开始的最短路径
    Closest[start].w = 0; //~
    k = start;
    for( int i = 0; i < n; ++i)
    {
        min = MAXINT;
        int t; //~ 维护下一个可以加入最短路径集的顶点
        Closest[k].v = true; //~ 加入最短路径集
        for(int j = 0; j < n; ++j) //~ 更新Closest和k
        {
            if(Closest[j].w > Closest[k].w + Adj[k][j])
            {
                Closest[j].w = Closest[k].w + Adj[k][j];
                Closest[j].src = k;
            }
            if(Closest[j].w < min && !Closest[j].v)
            {
                min = Closest[j].w;
                t = j;
            }
        }
        if(min == MAXINT) break; //~ 剩下的顶点不可达
        k = t;
    }
    //~ 下面代码供测试用
    for(int i = 0; i < n; ++i)
    {
        cout<<Closest[i].w<<'\t'<<boolalpha<<Closest[i].v<<endl;
    }
    while(cin>>to)
    {
        int rp = to;
        while(rp != start) //~ 反向输出路径
        {
            cout<<rp<<" <- ";
            rp = Closest[rp].src;
        }
        cout<<start<<endl;
    }
    return 0;
}
Tags: ,.
Filed under: 之算法神奇,边走编程 By dutor @ April 20th, 2010, 967 views Comments (2)
你好！除了代码，此处没有多少原创之物，皆为本人搜集、整理、总结之记录与心得，欢迎转载分享！转载时请尽量注明出处，将不胜感激。祝你健康、快乐！
«
»
Home

RFC: Request For Comments. Orz..

Name(required)
Mail (required),(will not be published)

RFC: Request For Comments. Orz..

Website(recommended)