一般实现

#include <bits/stdc++.h>
using namespace std;
#define NODE_NUM 5
#define M 1000
#define ERROR -1
#define INT32_MAX 1000

typedef struct GNode *PtrToGnode;
struct GNode{
    int nv = 5;
    int ne = 6;
    int Graph[NODE_NUM][NODE_NUM];
};
typedef PtrToGnode MGraph;

int FindMinDist(MGraph Graph, int dist[],int collected[]){
    int min_v, v;
    int min_dist = INT32_MAX;

    for(v = 0;v < Graph->nv;v++){
        if(collected[v] == false && dist[v]<min_dist){
            min_dist = dist[v];
            min_v = v;
        }
    }

    if(min_dist < INT32_MAX){
        return min_v;
    }else{
        return ERROR;
    }
}

bool dij(MGraph G, int dist[], int path[], int s){//s:start point
    int collected[G->nv];
    int v, w;
    //init
    for(v = 0;v < G->nv;v++){
        dist[v] = G->Graph[s][v];//init distance
        if(dist[v] < INT32_MAX){//对于源点邻接点来说，设置path，因为是从邻接矩阵第一行中获取的数据，等于MAX的事实上就是与源点不连通的点
            path[v] = s;
        }else{
            path[v] = -1;
        }
        collected[v] = false;//未收录除源点外的所有点。
    }
    dist[s] = 0;
    collected[s] = true;//初始化源点距离，收录

    while(1){
        v = FindMinDist(G,dist,collected);
        if(v == ERROR){
            break;
        }

        collected[v] = true;
        for(w = 0;w<G->nv;w++){
            if(G->Graph[v][w] < 0){
                return false;//dijkstra不允许存在负边
            }
            if(dist[v] + G->Graph[v][w] < dist[w]){//更新距离和前向点
                dist[w] = dist[v] + G->Graph[v][w];
                path[w] = v;
            }
        }
    }
    return true;
}

int main(int argc, char const *argv[])
{
    MGraph G = new struct GNode;
    G->nv = 5;
    G->ne = 6;
    int map[NODE_NUM][NODE_NUM] = 
        {
            {M,1,2,M,2},
            {1,M,M,3,M},
            {2,M,M,5,M},
            {M,3,5,M,4},
            {2,M,M,4,M}
        };
    //使用memcpy将map拷贝到G->Graph
    memcpy(G->Graph,map,sizeof(int)*NODE_NUM*NODE_NUM);

    int dist[NODE_NUM] = {0};
    int path[NODE_NUM] = {0};
    dij(G,dist,path,0);
    return 0;
}

堆优化

https://www.luogu.com.cn/problem/P4779

链式前向星

[[算法/数据结构/图#链式前向星]]