dijkstra的基本算法以及堆優化

dijkstra

基本算法 O(n^2)

是使用臨接矩陣儲存的，部分邊可能會被通路兩次，如果采用臨界表的話邊是但方向儲存的，隻需要通路一次，可以做略微的優化。

//
//  main.cpp
//  dijkstra
//
//  Created by 陳冉飛 on 2019/12/10.
//  Copyright © 2019 陳冉飛. All rights reserved.
//

#include <iostream>
using namespace std;
#define maxn 10010
#include <cstring>
#define cl(a,b) memset(a,b,sizeof(a))
int mp[maxn][maxn],d[maxn],vis[maxn],n,m,a,b,c; //n為點數，m為線段數
#define INF 1<<29

void dijkstra(){
    for (int i = 1; i <= n; i++) d[i] = mp[1][i];
    for (int i = 1; i <= n; i++) {
        int v = 0,tem = INF;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && d[j] < tem)
                tem = d[v=j];
        vis[v] = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && d[j] < d[v]+mp[v][j]) d[j] = d[v]+mp[v][j];
    }
    printf("%d\n",d[n]);
}

int main(int argc, const char * argv[]) {
    while (~scanf("%d%d",&n,&m)) {
        //init
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i == j) mp[i][j] = 0;
                else mp[i][j] = INF;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b] = mp[b][a] = c;
        }
        dijkstra();
    }
    return 0;
}
           

利用堆優化，用二維臨界表儲存資訊，放在一個向量表中，通過每個節點push新的結構體節點，包含索引和到那個點的距離等資料，然後來計算獲得圖表資訊。在init的時候要把自己到自己d數組的值初始化為零，在堆優化dijkstra函數中，把所有節點也以結構體儲存，通過類似廣搜的結構，通過在每次周遊該節點的所有情況的時候，把比目前好的情況都push進去隊列，(用一個維護最值的優先隊列，重載運算符，在每次被push進入隊列的時候就自動放在隊首)