849. Dijkstra求最短路 I

题目

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

思路

• Dijkstra适用于有向图或者无向图的非负边权图
• 稠密图用邻接矩阵存储
• ①.先将起点到其他节点的距离数组dist初始化为0x3f3f3f3f(看成无穷大)
• ②.遍历所有节点n-1次，每次对为处理的最短距离节点进行处理，查找未处理的最短距离节点，更新其到相邻节点的为较短距离
• ③.更新之后标记节点已经处理

代码

#include 
#include 

using namespace std;
const int N = 510;
int g[N][N];//邻接矩阵，存储节点之间的关系和边权
int dist[N];//1号点到各个节点的最短距离
bool st[N];//标记是否已经确定了节点的最短距离

int n, m;

int dijkstra(){
    // 1.初始化距离数组为最大值
    memset(dist, 0x3f, sizeof dist);
    // 2.设置起点到1号点的距离为0
    dist[1] = 0;
    // 3.查找n-1次，确定1号点到n-1个点的最短距离
    for(int i = 0; i < n-1; i++){
        // 4.查找最小的未确定的最短距离的节点的编号
        int minIndex = -1;
        for(int j = 1; j <= n; j++){
            if(!st[j] && (minIndex == -1 || dist[minIndex] > dist[j])) minIndex = j;
        }
        st[minIndex] = true;//标记已经确定当前点的最短距离
        
        //5.遍历邻接矩阵，访问当前节点的相邻节点，更新当前点到相邻节点的最小值
        for(int j = 1; j <= n; j++){
                dist[j] = min(dist[j], dist[minIndex] + g[minIndex][j]);//，更新当前点到相邻节点的最小值
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;//如果到达最终节点的距离已经被更新，则说明图连通
    return dist[n];//返回1号点到终点的最短距离
}

int main()
{
    cin >> n >> m;
    
    memset(g, 0x3f, sizeof g);//初始化邻接矩阵为最大值
    
    while(m -- ){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);//如果有重边，则保留较短边
    }
    
    int t = dijkstra();
    
    cout << t << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52