最短路算法 —— Dijkstra算法

用途：

解决单源最短路径问题（已固定一个起点，求它到其他所有点的最短路问题）

算法核心（广搜）：

（1）确定的与起点相邻的点的最短距离，再根据已确定最短距离的点更新其他与之相邻的点的最短距离。

（2）之后的更新不需要再关心最短距离已确定的点

三种实现模板：

一、矩阵朴素版

二、vector简单版

三、静态邻接表有点复杂版

#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;

//邻接矩阵

const int MAXN = 110;
int dis[MAXN];
int e[MAXN][MAXN];
bool vis[MAXN];
int N, M;

void dij()
{
    int p, mis;
    for(int i = 1; i <= N; i++)
        dis[i] = e[1][i];


    vis[1] = true;
    dis[1] = 0;
    for(int i = 1; i < N; i++)
    {
        mis = INF;
        for(int j = 1; j <= N; j++)
        {
            if(!vis[j] && dis[j] < mis)
            {
                mis = dis[j];
                p = j;
            }
        }
        vis[p] = true;

        for(int k = 1; k <= N; k++)
        {
            if(dis[k] > dis[p] + e[p][k] && !vis[k])
                dis[k] = dis[p] + e[p][k];
        }
    }
}

void init()
{
    for(int i  = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            if(i == j) e[i][j] = 0;
            else e[i][j] = INF;
    memset(vis, false, sizeof(vis));
}
int main()
{
    int a, b, c;
    while(~scanf("%d%d", &N, &M))
    {
        if(N == 0 && M == 0) break;
        init();
        while(M--)
        {
            scanf("%d%d%d", &a, &b, &c);
            e[a][b] = c;
            e[b][a] = c;
        }

        dij();
        printf("%d
", dis[N]);
    }

    return 0;
}



//vector 动态邻接表 + 优先队列

const int MAXN = 1e3 + 50;
struct edge
{
    int to, cost;
    edge(int vo = 0, int vt = 0):
        to(vo),cost(vt){}
};

vector<edge>G[MAXN];
typedef pair<int, int>P;
int dis[MAXN];
int N, M;

void init()
{
    for(int i = 1; i <= N; i++)
    {
        G[i].clear();
        dis[i] = INF;
    }

}
void Dijkstra(int s)
{
    int u, v;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0, s));
    dis[s] = 0;

    while(!que.empty())
    {
        P p = que.top(); que.pop();

        int u = p.second;
        if(dis[u] < p.first) continue;

        for(int i = 0; i < G[u].size(); i++)
        {
            edge v = G[u][i];
            if(dis[v.to] > dis[u] + v.cost)
            {
                dis[v.to] = dis[u] + v.cost;
                que.push(P(dis[v.to], v.to));
            }
        }
    }
}

int main()
{
    int u, v, c;
    scanf("%d%d", &N, &M);
    init();
    while(M--)
    {
        scanf("%d%d", &u, &v, &c);
        G[u].push_back(edge(v, c));
        //G[v].push(edge(u, c));  建无向图
    }

    //see see
    /*
    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < G[i].size(); j++)
            printf("%d ", G[i][j].to);
        puts("");
    }
    */

    Dijkstra(1);
    for(int i = 1; i <= N; i++)
        printf("%d ", dis[i]);
    puts("");

    return 0;
}




///静态邻接表 + 优先队列优化

const int MAXN = 1e3 + 50;
typedef pair<int, int> HeapNode;
struct edge
{
    int v, nxt, w;
}G[MAXN*100];
int head[MAXN], dis[MAXN];
int N, M, cnt;

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

inline void add(int from, int to, int we)
{
    G[cnt].w = we;
    G[cnt].v = to;
    G[cnt].nxt = head[from];
    head[from] = cnt++;
}

void dij()
{
    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;

        for(int i = head[T.second]; i != -1; i = G[i].nxt)
        {
            int v = G[i].v;
            if(dis[v] > dis[T.second] + G[i].w)
            {
                dis[v] = dis[T.second] + G[i].w;
                heap.push(make_pair(dis[v], v));
            }
        }
    }
}

int main()
{
    int a, b, c;
    while(~scanf("%d%d", &N, &M))
    {
        if(N == 0 && M == 0) break;
        init();
        while(M--)
        {
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }

        dij();
        printf("%d
", dis[N]);
    }

    return 0;
}