jtahstu的博客

root@jtahstu.com   Github   英文博客  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> 单源最短路径算法 - Dijkstra算法

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

7.1.png     7.2.png


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

算法


参考《啊哈算法》第六章第二节,

介绍

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

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

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

时间复杂度 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
 */


 2017-09-18 17:20 字数 1022 阅读 0



---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

45 + 79 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……