搜索与图论 - 朴素版Dijkstra算法

2020-09-25 09:45:32

Dijkstra算法是一种基于贪心的算法， 详情推导：

算法的基本思路：

  • 首先初始化每个点的距离是正无穷， 起点为0
  • 进行 n - 1 次循环
  • 每次找距离的最小值
  • 然后用距离的最小值去更新剩余点到起点的距离
  • 如果终点的距离为正无穷说明没有最短路

Acwing 849. Dijkstra求最短路 I

来源： https://www.acwing.com/problem/content/851/

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

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

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

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

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

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

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

输入样例：

1
2
3
4
3 3
1 2 2
2 3 1
1 3 4

输出样例：

1
3

C++实现：

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
// 由于是稠密图，所以用邻接矩阵的方式存储
// dist[i] 表示i 点到起点的距离
// st[i] 表示第i个点是否遍历过
int g[N][N];
int dist[N];
bool st[N];
int n, m;

int dijkstra()
{
    // 初始化所有点的距离为正无穷，起点距离为0
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 0; i < n - 1; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if (!st[j] && ( t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if (dist[n] == INF) return -1;
    return dist[n];
}

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);
    }

    cout << dijkstra() << endl;
    return 0;
}
  1. 1. Acwing 849. Dijkstra求最短路 I