单源最短路径算法 - Dijkstra算法

标签（空格分隔）： 算法

[TOC]

参考《啊哈算法》第六章第二节，PDF在线阅读

介绍

这是一个贪心算法，每次新扩展一个路程最短的点，更新与其相邻的点的路程。

这个算法可以解决单源最短路径问题，这里是从第一个点开始到其他点的最短路径。

不能有负权边，因为扩展到负权边的时候会产生更短的路程，有可能就破坏了已经更新的点路程不会改变的性质。

时间复杂度 O(N^2)，使用邻接表表示图，绝大部分情况下能降低时间复杂度，具体看PDF，我也没怎么看懂。

代码

/**
 * 单源最短路径算法
 * Dijkstra算法
 * 时间复杂度 O(N^2)
 * by jtahstu at 2017-09-18
 */
#include <iostream>
#include <climits>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int e[11][11] = {0}, dis[11] = {0}, book[11] = {0};
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = INT_MAX;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        e[a][b] = c;
    }
    for (int i = 1; i <= n; ++i) {
        dis[i] = e[1][i];
        book[i] = 0;
    }
    book[1] = 1;
    int min, u;
    for (int i = 1; i <= n - 1; ++i) {  //找出值最小的点去做中转，循环n-1次
        min = INT_MAX;
        for (int j = 1; j <= n; j++) {  //找到离1号顶点最近的顶点，然后该点最短路径值确定
            if (book[j] == 0 && min > dis[j]) {
                min = dis[j];
                u = j;
            }
        }
        book[u] = 1;    //标记该点最短路径值已经确定
        for (int v = 1; v <= n; v++) {
            if (dis[v] > dis[u] + e[u][v] && e[u][v] != INT_MAX) //有出边，且可以通过u点中转一下
                dis[v] = dis[u] + e[u][v];
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}

/**
6 8
1 2 1
1 3 2
2 3 3
2 4 3
2 5 1
3 4 5
4 6 2
5 6 1
0 1 2 4 2 3

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
0 1 8 4 13 17
 */