Dijkstra单源最短路径

基本思想

1. 假定一个源点u，顶点集合V被划分成两个部分：集合 S 和集合 V-S 。
2. 初始时S仅包含源点u，S中的顶点到源点u的最短距离已经确定，V-S中的顶点到源点u的最短距离待定。
3. 用数组dist[]记录每个顶点到源点u的最短距离。

算法流程

1. 数据结构：设地图的带权邻接矩阵为map[][]，如果源点u到顶点i有边，则map[u][i]为<u,i>的权值，否则map[u][i]为∞。利用一位数组dist[i]记录顶点i到源点u的最短路径。
2. 初始化， 令集合S = {u}，对于集合V-S中的所有顶点i，初始化dist[i]=map[u][i]。如果源点u与顶点i有边相连，初始化p[i]=u，否则p[i]=-1，p[]用来记录当前顶点i的前驱节点。
3. 找最小，在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t，即dist[t]=min(dist[j] | j属于V-S集合)，那么顶点t就是此时V-S中距离源点u最近的顶点。
4. 将t加入S集合， 同时更新V-S集合，也要更新与顶点t相连的其他顶点到源点u的距离。假设V-S集合中的顶点j与刚加入到S集合中的顶点t有边权值为map[t][i]，如果dist[j] > dist[t] + map[t][i]，则dist[j] = dist[t] + map[t][i]，且更新顶点j的前驱p[j]=t，否则dist[j]保持不变。
5. 判断集合S-V是否为空，若为空了，结束算法，否则跳转第3步。

最终dist[]数组记录了每个顶点到源点u的最短距离。
p[j]记录了顶点j到源点u的最短路径上的前驱节点，通过p[]能找到顶点j到源点u最短路径的路线。

一个简单的例子

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 100;//城市数量
const int INF = 1e7;//初始化无穷大值
int map[N][N], dist[N], p[N], n, m;//n为城市的个数，m为城市间路线的条数
bool flag[N];//flag[i]为true，表明顶点i已加入到集合S
void Dijkstra(int u)
{
    for(int i=1; i<=n; i++)
    {
        dist[i] = map[u][i];//初始化源点u到各个顶点的距离
        flag[i] = false;
        if(dist[i] == INF)
            p[i] = -1;//源点u到该顶点的距离无穷大，说明i点与源点不相邻
        else
            p[i] = u;
    }
    dist[u] = 0;
    flag[u] = true;//初始化时，集合S中只有一个元素，即源点u
    for(int i=1; i<=n; i++)
    {
        int temp = INF, t = u;
        for(int j=1; j<=n; j++)//在集合V-S中寻找距离源点u最近的顶点t
        {
            if(!flag[j]&&dist[j]<temp)
            {
                t = j;
                temp = dist[j];
            }
        }
        if(t==u) return;//找不到t，跳出循环
        flag[t] = true;//否则将t加入S集合
        for(int j=1; j<=n; j++)//更新集合V-S中与t相邻的顶点到源点u的距离
        {
            if(!flag[j]&&map[t][j]<INF)
                if(dist[j]>(dist[t]+map[t][j]))
                {
                    dist[j] = dist[t] + map[t][j];
                    p[j] = t;
                }
        }
    }
}
int main()
{
    int u, v, w, st;
    cout << "请输入城市的个数：" << endl;
    cin >> n;
    cout << "请输入城市之间路线的条数：" << endl;
    cin >> m;
    cout << "请输入城市之间的路线以及距离：" << endl;
    for(int i=1; i<=n; i++)//初始化邻接矩阵
        for(int j=1; j<=n; j++)
            map[i][j] = INF;//初始化邻接矩阵为无限大
    while(m--)
    {
        cin >> u >> v >> w;
        map[u][v] = min(map[u][v], w);//保留最小距离
    }
    cout << "请输入当前所在位置：" << endl;
    cin >> st;
    Dijkstra(st);
    cout << "起点所在位置：" << st << endl;
    for(int i=1; i<=n; i++)
    {
        cout << "起点：" << st << " - " << "目的地：" << i << " ";
        if(dist[i] == INF)
            cout << "无法到达" << endl;
        else
            cout << "最短距离为：" << dist[i] << endl;
    }
    return 0; 
}

输入和输出

请输入城市的个数：
5
请输入城市之间路线的条数：
11
请输入城市之间的路线以及距离：
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
请输入当前所在位置：
5
起点所在位置：5
起点：5 - 目的地：1 最短距离为：8
起点：5 - 目的地：2 最短距离为：24
起点：5 - 目的地：3 最短距离为：23
起点：5 - 目的地：4 最短距离为：30
起点：5 - 目的地：5 最短距离为：0

• 城市之间的距离是用有向图来表示的，路径表示都是单向的，如上面输入的1 5 12，是指城市1到城市5有一条路长度为12，不代表城市5到城市1有路可走。
• 若要表示无向图，输入1 5 12，默认城市5到城市1也有一条长度为12的路径即可。
• 代码中的p[]可以在有需要时用上，记录的城市i的前驱节点，这样可以依次找到从城市i到起点城市的逆向路径，使用栈逆序即可求出起点到各个顶点最短路径的路线了。

算法分析

1. 时间复杂度：O(n^2)
   • 最多只出现了两重循环且长度为n
2. 空间复杂度：O(n)
   • 辅助空间包括一维数组flag[]，i，j，t，temp

算法优化拓展

• 使用优先队列优化

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
const int N = 100;//城市数量
const int INF = 1e7;//初始化无穷大值
int map[N][N], dist[N], p[N], n, m;//n为城市的个数，m为城市间路线的条数
bool flag[N];//flag[i]为true，表明顶点i已加入到集合S
struct Node
{
    int u,step;
    Node(){};
    Node(int a, int sp)
    {
        u = a;
        step = sp;
    }
    bool operator < (const Node& a)const //重载  <
    {
        return step > a.step;
    }
};
void Dijkstra(int u)
{
    priority_queue <Node> Q; //优先队列优化
    Q.push(Node(u, 0));
    memset(flag, 0, sizeof(flag));//初始化flag数组为0
    for(int i=1; i<=n; i++)
        dist[i] = INF; //初始化所有距离为无限大
    dist[u] = 0;
    while(!Q.empty())
    {
        Node it = Q.top(); //优先队列对头元素为最小值
        Q.pop();
        int t = it.u;
        if(flag[t]) //说明已经找到了最短距离，该节点是队列里面的重复元素
            continue;
        flag[t] = true;
        for(int i=1; i<=n; i++)
        {
            if(!flag[i]&&map[t][i]<INF)
            {
                if(dist[i]>dist[t]+map[t][i])
                {
                    //求距离当前点的每个点的最短距离，进行松弛操作
                    dist[i] = dist[t] + map[t][i];
                    Q.push(Node(i, dist[i]));//把更新后的最短距离压入优先队列，里面会有重复元素
                }
            }
        }
    }
}
int main()
{
    int u, v, w, st;
    cout << "请输入城市的个数：" << endl;
    cin >> n;
    cout << "请输入城市之间路线的条数：" << endl;
    cin >> m;
    cout << "请输入城市之间的路线以及距离：" << endl;
    for(int i=1; i<=n; i++)//初始化邻接矩阵
        for(int j=1; j<=n; j++)
            map[i][j] = INF;//初始化邻接矩阵为无限大
    while(m--)
    {
        cin >> u >> v >> w;
        map[u][v] = min(map[u][v], w);//保留最小距离
    }
    cout << "请输入当前所在位置：" << endl;
    cin >> st;
    Dijkstra(st);
    cout << "起点所在位置：" << st << endl;
    for(int i=1; i<=n; i++)
    {
        cout << "起点：" << st << " - " << "目的地：" << i << " ";
        if(dist[i] == INF)
            cout << "无法到达" << endl;
        else
            cout << "最短距离为：" << dist[i] << endl;
    }
    return 0; 
}

1. 时间复杂度
   • while(!Q.empty()) 的执行次数为n，因为要弹出n个最小值队列才会为空
   • Q.pop()的时间复杂度为logn，while语句中的for语句执行n次，for语句中的Q.push()时间复杂度为logn
   • 因此，总的语句执行次数为nlogn+(n^2)logn，算法的时间复杂度为O((n^2)logn)

• 看似时间复杂度变大了，是因为采用的是邻接矩阵，如果采用邻接表，for语句的松弛操作就不用每次执行n次了，而是边的数量x，而每个节点的边加起来为E，总的时间复杂度为O(nlogn+Elogn)，当E>n时，时间复杂度为O(E*logn)。