資料結構 — 圖 之 MPT（最短路徑 — dijkstra算法 ）

【描述】：  無向圖的最短路徑 — Dijkstra(适用于非負權值邊）

【輸入】：

【輸出】：

頂點       距離（與源點）

0          0

1          3

2          5

3          4

4          4

/*
    Dijkstra(不适用于負權值的邊）
*/

#include<iostream>

using namespace std;

/* 宏定義 */
#define INFINITY 65535
#define MAX_NUM 100
#define EleType int

/* 定義一些需要的變量 */
bool visit[MAX_NUM];    //頂點i 是否已經走過了
int dist[MAX_NUM];    //源點到 頂點i 的距離
const int vertices = 5;    //頂點數

/* 定義圖 */

int graph[vertices][vertices] = {
    { 0,3,6,5,0 }, 
    { 3,0,0,1,1 },
    { 6,0,0,1,1 }, 
    { 5,1,1,0,1 },
    { 0,1,1,1,0 }
};

/* 通過dist數組得出得出當下到源點的最小頂點 */
int getMin() {
    int min = INFINITY;
    int minIndex;
    for(int i = 0; i<vertices; i++){
        if(!visit[i] && dist[i]<min){
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

/* dijkstra */
void dijkstra(int s){
    for(int i = 0; i<vertices; i++){
        if(graph[s][i] == 0){
            dist[i] = INFINITY;
        }else{
            dist[i] = graph[s][i];
        }
        visit[i] = false;
    }
    //源點距離為0，已經加入SPT
    dist[s] = 0;
    visit[s] = true;
    
    //更新dist數組
    for(int i = 1; i<vertices; i++){
        //得到dist數組中的最短距離的頂點
        //将其加入SPT
        int u = getMin();
        visit[u] = true;

        //更新
        for(int j = 0; j<vertices; j++){
            if(!visit[j] && dist[u]!=INFINITY && graph[u][j]!=0 && dist[u]+graph[u][j]<dist[j]){
                dist[j] = dist[u]+graph[u][j];
            }
        }
    }
}

/* 輸出函數 */
void print() {
    cout<<"頂點"<<"       "<<"距離（與源點）"<<endl;
    for(int i = 0; i<vertices; i++){
        cout<<i<<"          "<<dist[i]<<endl;
    }
}

int main(){
    
    dijkstra(0);
    cout<<endl;
    print();

    return 0;
}