适用条件

Dijkstra算法用于求边权全为正数的单源最短路径, 适合稠密图, 数据结构为邻接矩阵

C++ 代码

#include <iostream>
#include <cstring>      //使用memset()函数需要用到的头文件
using namespace std;

const int N = 510;

int n, m;
int dist[N];        //记录各个顶点到源点的最短距离
int g[N][N];        //记录图的信息
bool visited[N];    //记录各个顶点是否已被访问过

int dijkstra() {
    //1. 初始化
    memset(dist, 0x3f, sizeof dist);    //顶点间距离全部初始化为无穷大
    dist[1] = 0;            //源点(一般为第一个顶点，具体看题目)到自己的距离为0

    //2. 循环依次找到未被访问过且到源点距离最短的点
    for(int i = 0; i < n; i++) {
        int t = -1;     //记录每次未被访问过且到源点距离最短的点
        for(int j = 1; j <= n; j++) 
            //顶点j未被访问过 并且 t 要么等于-1, 要么存在非最短距离 
            if(!visited[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        visited[t] = true;  //置为已访问

        //3. 借助新被访问过的点更新源点到其他点的最短距离
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    if(dist[n] == 0x3f3f3f3f)  //若源点无法到达第n个点 
        return -1;

    return dist[n];            //源点可以到达第n个点, 距离为dist[n] 
}

int main() {
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);  //顶点间距离全部初始化为无穷大(INF = 0x3f3f3f3f算作一个小技巧)
    //memset()函数是按照字节初始化的，所以每个距离均为0x3f3f3f3f (int能表示的最大正整数，1e9级别的)

    for(int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);  //由于图中可能存在重边和自环，所以直接存储 a——>b 的一条最小边即可
    }

    printf("%d\n", dijkstra());

    return 0;
}