最短路 Dijkstra算法

Dijksitra算法求最短路僅僅適用于不存在右邊是負權的情況(Bellman-Ford算法沒有這一個限制)。主要特點是從起點為中心向外層層擴展，直到擴展到終點為止。

最短路的最優子結構性質

即一個最短路路徑中經過的所有點這條路均是其最短路。(反證法易證)

Dijkstra基本思路:
①找到最短距離已經確定的頂點，從它出發更新相鄰頂點的最短距離
②此后不需要再關心1中的”最短距離已經確定的頂點”

在最開始的時候，只有起點的最短距離是確定的。而在尚未使用過的頂點中，距離d[i]最小的頂點就是最短距離已經確定的頂點。由于不存在負邊，所以d[i]不會再之后的更新中變小。這就是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,d+V,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));
            }
        }
    }
}

Dijkstra算法的復雜度是O(|E|log|V|)，可以更加高效求解最短路。但如果有負邊還是要用Bellman-Ford算法。