dijkstra算法复习

dijkstra算法之前一直没有动手写，经过几次笔试之后，发现对这类问题不是很熟练。今天仔细研究了一下该算法的代码。用一种比较容易理解的方式给code出来。
首先，最直观的表示一个图的方法就是用邻接矩阵，虽然邻接矩阵效率不高，本代码中采用这种方法。
其次，C++中优先队列的使用需要重载<操作符。
最后，并没有对代码进行任何优化，所以十分容易理解。

#include <bits/stdc++.h>
using namespace std;
const int N = 6;
int mat[6][6] = {
        {0, 7, 9, INT_MAX, INT_MAX, INT_MAX},
        {7, 0, 10, 15, INT_MAX, INT_MAX},
        {9, 10, 0, 11, INT_MAX, 2},
        {INT_MAX, 15, 11, 0, 6, INT_MAX},
        {INT_MAX, INT_MAX, INT_MAX, 6, 0, 9},
        {INT_MAX, INT_MAX, 2, INT_MAX, 9, 0},
};
struct node{
    int id, w;
    bool operator < (const node &rhs) const {
        return w < rhs.w;
    }
};
int dis[N];
int main(){
    priority_queue<node> q;
    for(int i = 0; i < N; i++) dis[i] = INT_MAX;
    dis[0] = 0;
    q.push(node({0, 0}));
    while(!q.empty()){
        node x = q.top(); q.pop();
        for(int i = 0; i < N; i++) {
            if(mat[x.id][i] != INT_MAX && dis[i] > x.w + mat[x.id][i]) {
                dis[i] = x.w + mat[x.id][i];
                q.push(node({i, dis[i]}));
            }
        }
    }
    for(int i = 0; i < N; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}

唯一稍微不是十分直观的地方在第29行。代码中并没有在一开始就把除源点之外的所有点都放进优先队列里，而是每次找到最小的扩展点的时候，通过扩展点能缩短距离的那些边给放进优先队列里。