最短路径问题算法

Ⅰ 最短路径算法

最短路径的算法主要有三种：floyd算法、Dijkstra算法、Bellman-Ford(贝尔曼-福特)

一、floyd算法

基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。

三、Bellman-Ford(贝尔曼-福特)

算法的流程如下：

给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，

1.数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；

2.以下操作循环执行至多n-1次，n为顶点数：
对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

3.为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说该图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

Ⅱ 图文解析 | Dijkstra单源最短路径算法

给定 加权有向图 G=(V,E,W)，每条边的权值w为 非负数 ，表示两个顶点间的距离。

源点s∈V。

求：从s出发到其他各个顶点的最短路径。

如上图所示，以1为源点，计算到其余各个顶点的最短距离（我已用红线标出）。下面列出了最终解：

S集合 ：当从s到x（x ∈V ）的最短路径找到时，则x ∈S。当所有顶点都进入S集合时，算法结束。

初始：S=｛s｝，当S=V时算法结束。

从s到u相对于S的最短路径 ：指从s到u且仅经过S中顶点的最短路径。

dist[u]:从s到u相对于S的最短路径长度

short[u]:从s到u最短路径的长度（算法最终解）

dist[u] ≥ short[u]

Dijkstra算法采用贪心算法模式，算法过程就是通过计算dist[u],不断扩充S集合，同时dist[u]会不断优化改善，直到dist[u] = short[u]，并将其放到S中，当所有顶点都放入S集合时，算法结束。

输入：加权有向图G=(V,E,W)

          V={1,2,…,n}, s=1

输出：从s到每个顶点的最短路径

输入：G=(V,E,W)，源点1

          V={1,2,3,4,5,6}

初始S集合只有1，计算直接从1能到达的顶点的距离，其他不能从1号顶点直接到达的顶点都记为无穷大。雀轮睁此时从dist[u]里找出最短距离的顶点（6号），并将其放进S集合。

  S={1}

  dist[1] = 0

  dist[2] = 10

  dist[6 ] = 3

  dist[3] = ∞

  dist[4] = ∞

  dist[5] = ∞

当把6号顶点放进S集合后，经由6号顶点出发到达的顶点的最短距离可能会被优化更新，因为该算法的思想很“贪心”，谁更短我要谁！比如1->6->2要比1->2距离更短，所以dist[2]被更顷岁新为5，从专业术语上讲，这个“更新”过程叫做松弛，其他点同理。然桐唤后从dist[u]里找出最短的路径的那个顶点（5号），并放进S集合里。

  S={1,6}

  dist[1] = 0

 dist[6] = 3

  dist[2] = 5

  dist[4] = 9

  dist[5] = 4

  dist[3] = ∞

后面的操作步骤其实就是重复上面的操作。即当S集合里有个新的顶点后，就可能会更新其他点的最短距离，更新一遍后，找出当前最短距离的dist[u]，并将该顶点放进S集合。后面不重复阐述。

  S={1,6,5}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

  dist[2] = 5

  dist[4] = 9

  dist[3] = ∞

  S={1,6,5,2}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

 dist[2] = 5

  dist[4] = 9

  dist[3] = 12

  S={1,6,5,2,4}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

 dist[2] = 5

 dist[4] = 9

  dist[3] = 12

  S={1,6,5,2,4,3}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

 dist[2] = 5

 dist[4] = 9

 dist[3] = 12

当有向图中的所有顶点都进入了S集合后，算法结束，此时的dist[u]的值其实就是最初我们找出的那个最终解short[u]，所以，算法结束时，dist[u]=short[u],得到最终解。

Ⅲ 最短路径 - Dijkstra算法

算法每次都查找距离起始点最近的点，那么剩下的点距离起始点的距离一定比当前点大。

1.选定A节点并初始化，如上述步骤3所示

2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合

3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离 其实为 A->D->B

思路就是这样，往后就是大同小异了
算法结束

（图片来源于网络）

Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。在上图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）。因而Dijkstra算法可以找到一条最短的路径，但是效率上并不高。

数据结构--Dijkstra算法最清楚的讲解

Ⅳ 图遍历算法之最短路径Dijkstra算法

最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：

常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。

Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决着名的旅行商问题。

问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。

为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。

以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：

注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进

第2步 ：选取顶点 添加进 ，更新 中顶点最短距离

第3步 ：选取顶点 添加进 ，更新 中顶点最短距离

第4步 ：选取顶点 添加进 ，更新 中顶点最短距离

第5步 ：选取顶点 添加进 ，更新 中顶点最短距离

第6步 ：选取顶点 添加进 ，更新 中顶点最短距离

第7步 ：选取顶点 添加进 ，更新 中顶点最短距离

示例：node编号1-7分别代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))输出结果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))输出结果：

示例：

找到D（4）到G（7）的最短路径：

[1] 维基网络，最短路径问题： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/