最短路 Dijkstra算法

最短路的最优子结构性质

未优化的Dijkstra算法代码

int cost[max_v][max_v]; //使用邻接矩阵储存边(不存在就是INF)
int d[max_v]; //最短距离
bool used[max_v]; //已经确定最短路的图
int V;

//Dijkstra算法
void dijkstra(int s)
{
    //初始化
    fill(d,d+V,INF);
    fill(used,used+V,false);
    d[s] = 0;

    //最短路
    while(true) {
        int v = -1;
        for(int i = 0 ; i < V ; i ++) {
            if(!used[i]) {
                if(v == -1 || d[i] < d[v]) v = i;
            }
        }
        if(v == -1) break;//如果都确定了就退出
        used[v] = true;
        for(int i = 0 ; i < V ; i ++) {
            d[i] = min(d[i],d[v]+cost[v][i]);
        }
    }
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge{int to,cost;};
typedef pair<int,int> P; //first是最短距离 second是顶点编号
int V;
vector<edge> G[max_v];//邻接表
int d[max_v];
void dijkstra(int s)
{
    //通过指定greater<P>参数，堆按照first从小到大的顺序取出值
    priority_queue<P,vector<P>,greater<P>> que;
    fill(d,INF);
    d[s] = 0;
    que.push(P(0,s));
    while(!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;//编号
        if(d[v] < p.first) continue;
        for(int i = 0 ; i < G[v].size() ; i ++) {
            edge e = G[v][i];
            if(d[e.to] > d[v]+e.cost) {
                d[e.to] = d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}