經典算法——迪傑斯特拉（Dijkstra）最短路徑

基本思想

迪傑斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，是以又叫狄克斯特拉算法。是從一個頂點到其餘各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪傑斯特拉算法主要特點是以起始點為中心向外層層擴充，直到擴充到終點為止。

其基本思想是，設定頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。

初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間隻經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄目前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，将u添加到S中，同時更新數組dist（算導中稱作Relax）。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。

僞代碼

Dijkstra（G,w,s）

1. Initializ_single_source(G,s) //dist[] = INF, dist[s] = 0

2. S = 空集

3. Q=G.V

4. while Q != 空集

u = Extract-Min(Q)

S = SU{u}

for each vertex v屬于G.adj[u]

Relax(u,v,w)

C++實作

#include<iostream>
#include<vector>
#include<stack>
//#include<limits.h>
using namespace std;

struct edge{
    int noEnd; //邊的終點序号
    int w;  
    edge(int _no, int _w):noEnd(_no),w(_w){}
};

class Graph{
private:
    vector<vector<edge>> Edge; //鄰接表
    vector<int> dist;
    vector<char> vertex; // 頂點資訊
    int n; // 頂點個數
    int e; //邊數
    vector<int> path; //記錄着從源點v0到目前點最短路徑的前驅節點序号
public:
    Graph(int _n, int _e):n(_n),e(_e){
        vertex.resize(n+);  //計數序号從1開始
        Edge.resize(n+);
        path.resize(n+);
        dist.resize(n+);
        //初始化
        for(int i=; i<=n; i++){
            path[i] = -;
            dist[i] = INT_MAX;
        }
    }

    //依次讀入頂點資訊
    void readVertex(){
        cout<<"請依次輸入頂點資訊："<<endl;
        for(int i=; i<=n; i++) cin>>vertex[i];
    }

    //依次讀入邊資訊
    void readEdge(){
        cout<<"請依次輸入邊資訊source,dst,weight："<<endl;
        int r,d,w; //r、d、w分别表示起點、終點、權重
        for(int i=; i<=e; i++){
            cin>>r>>d>>w;
            Edge[r].push_back(edge(d,w));
            // Edge[d].push_back(edge(r,w)) 無向圖
        }
    }
    void Dijkstra(int v0);
    // v0是源點
    void printPath(int v, int v0){
        stack<int> s;       
        while(v != v0){
            s.push(v);
            v = path[v];
        }
        cout<<endl<<vertex[v0];
        while(!s.empty()){
            v = s.top();
            s.pop();
            cout<<"->"<<vertex[v];
        }
        cout<<endl;
    }
};

void Graph::Dijkstra(int v0){   
    dist[v0] = ;
    vector<bool> isVisited(n+,false);
    isVisited[v0] = true;
    for(int i=; i<Edge[v0].size(); i++){
        edge tmp = Edge[v0][i];
        if(dist[v0] + tmp.w < dist[tmp.noEnd]){
             dist[tmp.noEnd] = dist[v0] + tmp.w;
             path[tmp.noEnd] = v0;
        }
    }
    int N=n-;
    while(N--){

        //找到下一個加入S集合中的點
        int u = -;
        int tmpMin = INT_MAX;
        for(int i=; i<=n; i++){
            if(!isVisited[i] && dist[i] < tmpMin){
                u = i;
                tmpMin = dist[i];           
            }
        }
        isVisited[u] = true; 

        //Relax 更新dist
        for(int i=; i<Edge[u].size(); i++){
            edge tmp = Edge[u][i];
            if(dist[u] + tmp.w < dist[tmp.noEnd]){
                 dist[tmp.noEnd] = dist[v0] + tmp.w;
                 path[tmp.noEnd] = u;
            }
        }
    }
}

int main(){
    int n,e;
    cout<<"請輸入頂點數，邊數："<<endl;
    cin>>n>>e;
    Graph graph(n,e);

    graph.readVertex();
    graph.readEdge();

    int v0, v;
    cout<<"請輸入源點及終點序号:"<<endl;
    cin>>v0>>v;
    graph.Dijkstra(v0);
    graph.printPath(v,v0);
    cout<<endl;
}