美文网首页
图的最短路径算法

图的最短路径算法

作者: dounine | 来源:发表于2019-02-20 12:29 被阅读0次

0. 前言

本文将介绍求解图最短路径的三个经典算法:迪杰斯特拉 Dijkstra、弗洛伊德 Floyd、贝尔曼-福特 Bellman-Ford。

1. 迪杰斯特拉 Dijkstra

迪杰斯特拉算法,用于解决 “给定起始点到其余点的最短路径” 问题,即单源最短路径算法。时间复杂度为 O(n^2)。其本质是贪心

算法步骤为:

  1. G[n][n] 二维数组记录图数据;定义 dis[n] 一维数组记录起始点到各点的最短路径,初始化为 INF(可以是 int 的最大值);visited[n] 一维数组记录该点是否给访问过(“访问过”表示已找到最短路径),初始化为 false
  2. 选择起始点 s ,令 dis[s] == 0
  3. 进行 n 次循环:
    1. 先从 dis[n] 数组的所有未访问结点中,找出最小值,并记录对应下标 p ,令 visited[p] = true
    2. 更新 p 所有邻接点在 dis[n] 数组中的值,更新规则为:dis[i] = min{dis[i], dis[p]+G[p][i]}

示例及图解:

D1.png D2.png D3.png D4.png D5.png

核心伪代码如下:

int dis[n];
bool visited[n];
for (int i = 0; i < n; i++) {
    dis[i] = INF;
    visited[i] = false;
}

dis[s] = 0;
for (int j = 0; j < n; j++) {
    // 找 dis 数组中的最小值
    int p = -1, min = INF;
    for (int i = 0; i < n; i++) {
        if (visited[i] == false && dis[i] < min) {
            p = i;
            min = dis[i];
        }
    }
    visited[p] = true;

    // 更新最小值所有邻接点的值
    for (int i = 0; i < n; i++) {
        if (G[p][i] == INF || visited[i]) continue;
        if (dis[i] > dis[p]+G[p][i]) {
            dis[i] = dis[p] + G[p][i];
        }
    }
}

2. 弗洛伊德 Floyd

弗洛伊德是求解图中任意两点间最短路径的算法。时间复杂度为 O(n^3)。其本质是动态规划

算法步骤为:

  1. 任意两点间的最短距离用 d(x,y) 表示,初始值为两点相连边的权重。

  2. 遍历所有点 k,若任意两点 i 和 j,满足 d(i,j) > d(i,k) + d(k,j),则 d(i,j) = d(i,k) + d(k,j)

代码如下:

for (k = 1; k <= n; k++) {
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
}

算法分析:Floyd 的核心思想是动态规划。

  1. 我们先定义状态:d[k][i][j],它表示经过前 k 个节点,点 i 到点 j 的最短路径。

  2. d[k][i][j] 可以由 d[k-1][i][j] 转移而来:

    • 假设已经求出,经过前 k-1 个节点,任意两点间的最短路径。
    • 那么,d[k][i][j] 就是 经过前 k-1 个节点 i 到 j 最短路径经过第 k 个节点 i 到 j 最短路径 中的最小值。
    • 而经过第 k 个节点 i 到 j 最短路径,就是 i 到 k 的最短路径加上 k 到 j 的最短路径。
    • 最终,得出状态转移方程为:d[k][i][j] = min{d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]}
  3. 由于 d[k][x][x] 的状态仅由 d[k-1][x][x] 转移而来,所以我们可以进行优化:d[i][j] = min{d[i][j], d[i][k] + d[k][j]}

3. 贝尔曼-福特 Bellman-Ford

贝尔曼-福特算法,也是一个单源最短路径算法,同时它还能处理负权边。算法时间复杂度为 O(NE)N 是点的个数,E 是边的个数。

算法步骤:

  1. 令源点为 s ,源点到任意点 x 的最短距离用 d(x) 表示。d(s) 初始值为0,其余初始值为无穷。

  2. 进行 N-1 次松弛操作,松弛操作即:遍历所有边,对于每一条边 e(i,j) ,如果存在 d(j) > d(i) + e(i,j) ,则令 d(j) = d(i) + e(i,j)

代码如下:

for (i = 0; i < n-1; i++) {
    for (j = 0; j < E; j++) {
        if (d(e[j].to) > d(e[j].from) + e[j]) {
            d(e[j].to) = d(e[j].from) + e[j];
        }
    }
}

算法分析:松弛操作的过程十分神奇,直觉告诉我它肯定是正确的,但具体原因我也是一头雾水。不过,我们可以知道,每次松弛操作后,至少能确定一个点的最短路径。所以,需要进行 N-1 次。

Bellman-Ford 如何解决 Dijkstra 不能解决的负权边问题呢?如下图,源点为 1 。若在 Dijkstra 中,第二次大循环时便会确定源点到点 3 的最短距离为 1 ;而在 Bellman-Ford 中,经过松弛操作便可以确定源点到点 3 的最短距离为 -1 。

6.png

Bellman-Ford 算法虽然能解决负权边的问题,但时间复杂度还是偏高,当用于稠密图时,是无法接受的。

因此,有人提出了 Bellman-Ford 的优化算法:SPFA。即第一次松弛操作,只需要对源点的邻接边进行即可;第二次松弛操作,只需要对与这些边相连点的邻接边进行即可;以此类推,直至所有边遍历完。这类似于 BSF 。

4. 参考

【原创】算法系列——四种最短路算法:Floyd,Dijkstra,Bellman-Ford,SPFA

相关文章

  • 图的应用-最短路径求解

    图的最短路径   图的最短路径是一个起点到一个终点之间最短的路径。  用于解决最短路径问题的算法被称做“最短路径算...

  • 头条-手撕代码

    [toc] 图算法 以及最短路径算法 树算法 手写LRU 排序算法 链表算法

  • python 狄克斯特拉算法

    前言 狄克斯特拉算法是解决加权图求最短路径的算法,广度优先算法可以求非加权图的最短路径,但是如果图的边权重不一样,...

  • 数据结构与算法学习 (14)最短路径求解

    最短路径问题是图研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形...

  • 数据结构与算法-最短路径问题

    最短路径问题是图研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形...

  • 最短路径算法(D算法)

    解决最短路径算法的D算法,是一个解决从点到点之间最短路径的问题,看下面这张图:

  • 19-图的最短路径

    图的最短路径 迪杰斯特拉算法 贝尔曼-福特算法 弗洛伊德算法 SPFA算法(中国西南交通大学段凡丁发明) 最短路径...

  • Graphx图算法【4】最短路径 ShortestPaths

    Graphx的最短路径算法只针对非带权图(即边的权重相等),采用迪杰斯特拉算法。 4.1 简介 最短路径算法用来计...

  • 遍历 最短路径 1.单源最短路 有权图-Dijkstra 多源头最短路-Floyd算法 —————————————...

  • java最短路径(jgrapht)

    基于jgrapht求最短路径的算法,有向图/无向图,加权图

网友评论

      本文标题:图的最短路径算法

      本文链接:https://www.haomeiwen.com/subject/slzcyqtx.html