最短路 Dijkstra 算法详解与模板

图解1

Dijkstra 使用的是贪心的思想，先假设所有顶点之间都没有边相连，然后每次从输入的边中选取一条权值最小的边并连接该边所对应的两个顶点，直到最后所有的顶点都被连通为止（即所有的顶点都能通过某一路径走到指定的点),如下图 以顶点（1）为起点，点（1）连通有（6），（3），（2）三个点，权值分别为14,9,7（其他点赋值为无穷大）; 所以选择权值最小的7,并连接（1,2）这条边（这里是通过并查集把两个点并入同一个祖先实现的） 然后再次遍历存权值的数组，找出下一个没被使用过且权值最小的边，并入集合中，这样一直循环n-1次，遍历了n-1个顶点之后，dis[j]就为从起点a->j的最短距离。 算法时间复杂度为O(n^2) (可以用堆或者优先队列优化达到更低的时间复杂度，可是我不会= =…..)

图解2

GIF图解如下： 所以每次需要执行的就是- ->找一条没有被标记且权值最小的边 ->将该边所连的顶点标记 ->将记录距离的数组更新 ->重复第一步 需要注意的是，一开始设距离为无穷大，如果一圈找完后还是存在距离=无穷大，那么说明剩下的顶点与集合内的顶点均不连通. 起点以左下角的红点 目标是右上角的绿点 中间灰色的倒L型为障碍物 蓝色空圈表示”暂定“，用以搜索下一步；已经填充颜色的表示探访过，图中颜色以红到绿，越绿表示离起点越远。所有节点都被均匀的探索。

代码(朴素版)

代码初学时可能看着比较难以理解，但是自己试着抄一下，每一行每一行的看下来会发现还是很好理解的 本份代码无任何优化,时间复杂度$O(n^2)$,空间复杂度$O(n^2)$ 已通过 HDU2544 完成了正确性验证 以下是代码模板

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define IN freopen("in.txt","r",stdin)
using namespace std;
const int maxn = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int inf = 0x3f;
typedef long long ll;
int n, m;

int dis[maxn];  ///a到各点的距离
bool vis[maxn]; ///标记该点是否已经使用

int map[maxn][maxn];
void dijkstra(int a)
{
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= n; i++)
        dis[i] = map[a][i];
    dis[a] = 0;
    vis[a] = true;
    for (int i = 1; i <= n; i++)
    {
        int Min = INF, Np = a;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] < Min)
            {
                Np = j;
                Min = dis[j];
            }
        if (Np == a)
            return;
        vis[Np] = true;
        for (int j = 1; j <= n; j++)
            if (dis[j] > (dis[Np] + map[Np][j]))
                dis[j] = dis[Np] + map[Np][j];
    }
}
void init(int n){
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            map[i][j] = INF;
    memset(vis, 0, sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
}
int main()
{
    //  IN;
    int a, b, c;
    while (cin >> n >> m && (n || m))
    {
        init(n);
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b >> c;
            map[a][b] = map[b][a] = min(map[a][b],c); //本题有重边,所以得取最小
        }
        dijkstra(1);
        cout << dis[n] << endl;
    }
    return 0;
}

代码(堆优化版本)

其实我们可以观察到, Dijkstra 算法 找最小权值的边 比较耗时，大部分的时间都花在了查找下一个使用的顶点上，因此需要使用合适的数据结构进行优化。如果说我现在可以选择的边权(如果该边连接的两个点一个已经被选择过,另一个点未被选择,则说这条边是可选择的)有${4,6,2,3,6}$,那么一定是选择最短边所连接的点进行更新.这样,通过每次选择最短边进行更新,可以避免大量无谓的时间消耗.其中,$m$表示边数,$n$表示点数 本份代码通过 链式前向星 和 二叉堆 将 Dijkstra 的空间复杂度优化到了 $O(E)$, 时间复杂度优化到了$O((E+V)logV)$.其中,$E$表示边数,$V$表示点数 已通过 HDU2544 完成了正确性验证

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <cstring>
#include <map>
#include <cmath>
#define IN freopen("in.txt", "r", stdin);
using namespace std;
typedef long long int ll;
const int maxn = 1e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int head[maxn];
int cnt;
struct edge
{
    int next;
    int v;
    int w;
} e[maxn];

void addEdge(int u, int v, int w)
{
    e[++cnt] = {head[u] ,v, w};
    head[u] = cnt;
}
struct node
{
    int dis, id;
    bool operator<(const node &a) const
    {
        return dis > a.dis;
    }
};
int dis[maxn];
bool vis[maxn];
void Dijkstra(int s)
{
    node buf;
    dis[s] = 0;
    priority_queue<node> q;
    q.push({0, s});
    while (!q.empty())
    {
        buf = q.top();
        q.pop();
        if (vis[buf.id])
            continue;
        vis[buf.id] = true;
        for (int i = head[buf.id]; i; i = e[i].next)
        {
            int v = e[i].v;
            int w = e[i].w;
            if (buf.dis + w < dis[v])
            {
                dis[v] = buf.dis + w;
                q.push({dis[v], v});
            }
        }
    }
}
void init(int n)
{
    cnt = 0;
    fill(dis, dis + n + 5, INF);
    fill(vis, vis + n + 5, 0);
    memset(head, 0, sizeof(head));
    memset(e, 0, sizeof(e));
}
int main()
{
    // IN;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> n >> m && (n || m))
    {
        init(n);
        int u, v, w;
        for (int i = 0; i < m; i++)
        {
            cin >> u >> v >> w;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        Dijkstra(1);
        cout << dis[n] << endl;
    }
}