Dijkstra算法求最短路模板

Dijkstra算法适合求不包含负权路的最短路径，通过点增广、在稠密图中使用优化过的版本速度非常可观。本篇不介绍算法原理、只给出模板，这里给出三种模板，其中最实用的是加上了堆优化的版本

算法原理 or 学习参考链接 : 点我 、不要点它点我！、为何不适用于带负权边图       

          

               ( Dijkstra 动态演示 )

朴素版 ( 邻接矩阵存储、复杂度 O( n2 ) )

///HDU 2544为例
#include<stdio.h>
#include<string.h>
const int INF  = 0x3f3f3f3f;
const int maxn =  1001;

bool vis[maxn];
int G[maxn][maxn],dis[maxn],pre[maxn];//pre[]记录前驱、用于输出路径
int n, m;
void dijkstra(int v)
{
    int i, j, u , Min;
    for(i=0;i<=n;i++){
        dis[i]=G[v][i];
        vis[i]=0;
        //if(i!=v&&G[v][i]!=INF)pre[i] = v;
       // else pre[i] = -1;
    }
    vis[v]=1;dis[v]=0;
    for(i=1;i<n;i++){
        Min = INF;
        for(j=1;j<=n;j++){
            if(!vis[j]&&Min > dis[j]){
                Min = dis[j];
                u = j;
            }
        }
        if(Min == INF)break;
        vis[u]=1;
        for(j=1;j<=n;j++){
            if(!vis[j]&&G[u][j]!=INF&&dis[u]+G[u][j]<dis[j]){
                dis[j] = G[u][j] + dis[u];
              //  pre[j] = u;
            }
        }
    }
}
int main()
{
    int i, j, x, y, w;
    while(~scanf("%d%d",&n,&m)&&n)
    {
        for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
                if(i==j)G[i][j]=0;
                else G[i][j] = INF;

        while(m--){
            scanf("%d%d%d",&x,&y,&w);
            G[x][y] = w;
            G[y][x] = w;
        }
        dijkstra(1);
        printf("%d
",dis[n]);  //以下为输出路径
        /*int p, len=0, ans[maxn];
        p = n-1;
        while(p!=0)
        {
            ans[len++] = p;
            p = pre[p];

        }
        printf("0->");
        for(i=len-1;i>=0;i--)
            printf("%d",ans[i]);
        puts("");  */
    }
    return 0;
}
View Code

STL优先队列优化版本 ( 复杂度 O( (V+E)logV ) )、此优化需要用邻接表存图

///POJ 2387为例
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int maxn = 1e3 + 50;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> HeapNode;///在堆里面的是pair、first为到起点距离、second为点编号
struct EDGE{ int v, nxt, w; };

int Head[maxn], Dis[maxn];
EDGE Edge[maxn*100];
int N, M, cnt;

inline void init()
{
    for(int i=0; i<=N; i++)
        Head[i]=-1, Dis[i]=INF;
    cnt = 0;
}

inline void AddEdge(int from, int to, int weight)
{
    Edge[cnt].w = weight;
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

int Dijkstra()
{
    priority_queue<HeapNode, vector<HeapNode>, greater<HeapNode> > Heap;
    Dis[1] = 0;
    Heap.push(make_pair(0, 1));
    while(!Heap.empty()){
        pair<int, int> T = Heap.top(); Heap.pop();
        if(T.first != Dis[T.second]) continue;///有很多版本都是用 vis 标记是否已经使用这个点松弛过、这里可以用这个不同的方法！
        
        for(int i=Head[T.second]; i!=-1; i=Edge[i].nxt){
            int Eiv = Edge[i].v;
            if(Dis[Eiv] > Dis[T.second] + Edge[i].w){
                Dis[Eiv] = Dis[T.second] + Edge[i].w;
                Heap.push(make_pair(Dis[Eiv], Eiv));
            }
        }
    }
    return Dis[N];
}

int main(void)
{
    while(~scanf("%d %d", &M, &N)){

        init();

        int from, to, weight;
        for(int i=0; i<M; i++){
            scanf("%d %d %d", &from, &to, &weight);
            AddEdge(from, to, weight);
            AddEdge(to, from, weight);
        }

        printf("%d
", Dijkstra());
    }
    return 0;
}
View Code

传说中还有一种斐波那契堆，比STL默认的堆更高效、但是斐波那契堆难写难理解、故用配对堆来代替( 复杂度 O(VlogV + E) )

///POJ 2387为例
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
using namespace std;
const int maxn = 1e3 + 10;
const int INF  = 0x3f3f3f3f;
struct EDGE{ int v, nxt, w; };
EDGE Edge[maxn*maxn];
int Head[maxn], Dis[maxn], T, N, cnt;
int Cost[maxn][maxn];
inline void init()
{
    for(int i=0; i<=N; i++){
        Head[i]=-1,Dis[i]=INF;
        for(int j=0; j<=N; j++){
            Cost[i][j] = INF;
        }
    }
    cnt=0;
}

inline void ADD(int from, int to, int weight)
{
    Edge[cnt].w=weight,
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

struct Heap{
    int num[maxn],pos[maxn],Size;

    void PushUp(int p) {
        while(p > 1) {
            if(Dis[num[p]] < Dis[num[p >> 1]]) {
                swap(num[p],num[p >> 1]);
                swap(pos[num[p]],pos[num[p >> 1]]);
                p >>= 1;
            }
            else break;
        }
    }
    void Insert(long long x) {
        num[++Size] = x;
        pos[x] = Size;
        PushUp(Size);
    }
    void Pop() {
        pos[num[1]] = 0;
        num[1] = num[Size--];
        if(Size)    pos[num[1]] = 1;
        int now = 2;
        while(now < Size) {
            if(Dis[num[now + 1]] < Dis[num[now]])
                ++now;
            if(Dis[num[now]] < Dis[num[now >> 1]]) {
                swap(num[now],num[now >> 1]);
                swap(pos[num[now]],pos[num[now >> 1]]);
                now <<= 1;
            }
            else break;
        }
    }
}heap;///配对堆

int Dijkstra()
{
    Dis[1] = 0;
    for(int i=1; i<=N; i++) heap.Insert(i);
    while(heap.Size){
        int x = heap.num[1]; heap.Pop();
        for(int i=Head[x]; i!=-1; i=Edge[i].nxt)
            if(Dis[Edge[i].v] > Dis[x] + Edge[i].w)
                Dis[Edge[i].v] = Dis[x] + Edge[i].w,
                heap.PushUp(heap.pos[Edge[i].v]);
    }
    return Dis[N];
}

int main(void)
{
    while(~scanf("%d %d", &T, &N)){

        init();

        int from, to, weight;
        for(int i=0; i<T; i++){
            scanf("%d %d %d", &from, &to, &weight);
            if(Cost[from][to] > weight){
                Cost[from][to] = Cost[to][from] = weight;
                ADD(from, to, weight);
                ADD(to, from, weight);
            }
        }

        printf("%d
", Dijkstra());
    }
    return 0;
}
手撕配对堆版本

在 Linux 下有pbds可以调用，里面可以调用二叉堆、配对堆、斐波那契堆……

///POJ 2387为例
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>///记得加上
#include<stdlib.h>
using namespace __gnu_pbds;///记得加上
using namespace std;
const int maxn = 1e3 + 5;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> HeapNode;
struct EDGE{ int v, nxt, w; };

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int Head[maxn], Dis[maxn];
EDGE Edge[maxn*100];
int N, M, cnt;

inline void init()
{
    for(int i=0; i<=N; i++)
        Head[i]=-1, Dis[i]=INF;
    cnt = 0;
}

inline void AddEdge(int from, int to, int weight)
{
    Edge[cnt].w = weight;
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

int Dijkstra()
{
    __gnu_pbds::priority_queue<HeapNode,greater<HeapNode>,pairing_heap_tag > Heap;///申请方式、其余和普通优先队列无差别
    Dis[1] = 0;
    Heap.push(make_pair(0, 1));
    while(!Heap.empty()){
        pair<int, int> Top = Heap.top();
        Heap.pop();
        int v = Top.second;
        if(Top.first != Dis[v]) continue;
        for(int i=Head[v]; i!=-1; i=Edge[i].nxt){
            int tmp = Edge[i].v;
            if(Dis[tmp] > Dis[v] + Edge[i].w){
                Dis[tmp] = Dis[v] + Edge[i].w;
                Heap.push(make_pair(Dis[tmp], tmp));
            }
        }
    }
    return Dis[N];
}

int main(void)
{
    while(~scanf("%d %d", &M, &N)){

        init();

        int from, to, weight;
        for(int i=0; i<M; i++){
            from = read(); to = read(); weight = read();
            AddEdge(from, to, weight);
            AddEdge(to, from, weight);
        }

        printf("%d
", Dijkstra());
    }
    return 0;
}
pbds
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qwertiLH/p/7687600.html