weixin_40725706

这个屌丝很懒，什么也没留下！

热门标签

最短路径问题相关算法、原理及适用场景_最短路径算法

作者：weixin_40725706 | 2024-07-06 02:37:39

踩

最短路径算法

这里写目录标题

一、最短路径算法、原理及适用场景
二、k最短路径问题（K-Shortest Path Problem）
- 基于Yen算法的k最短路径问题
三、Networkx中最短路算法使用
- 单源最短路算法

一、最短路径算法、原理及适用场景

深度优先搜索算法/广度优先搜索算法

从起始结点开始访问所有的深度遍历路径或广度优先路径，则到达终点结点的路径有多条，取其中路径权值最短的一条则为最短路径。

算法思想：深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为 $O (V!)$ 。
应用场景：单源最短路径算法，不能求含负权边的图
算法时间复杂度： $O (V!)$
深度优先搜索求解最短路问题完整代码：

import copy
import itertools


class DFS:
    def __init__(self, graph):
        self.adjacent_list = graph

    def run(self, source, target):

        # 深度优先搜索遍历，获取source-target的所有路径
        path = []
        paths = []
        self.helper(source, target, path, paths)

        # 返回最短路径，及距离
        shortest_path = None
        shortest_distance = 1 << 31
        for path in paths:
            distance = 0
            for i, j in itertools.pairwise(path):
                distance += self.get_distance(i, j)
            if distance < shortest_distance:
                shortest_distance = distance
                shortest_path = path

        return shortest_path, shortest_distance

    def helper(self, source, target, path, paths):
        current = source
        path.append(current)

        if current == target:
            paths.append(copy.deepcopy(path))
            path.remove(current)
            return
        neighbors = self.get_neighbors(current)

        for neighbor in neighbors:
            self.helper(neighbor, target, path, paths)
        path.remove(current)

    def get_neighbors(self, node):
        neighbor_weight_list = self.adjacent_list[node]
        neighbors = []
        for neighbor, weight in neighbor_weight_list:
            neighbors.append(neighbor)
        return neighbors

    def get_distance(self, i, j):
        neighbor_weight_list = self.adjacent_list[i]
        for neighbor, weight in neighbor_weight_list:
            if neighbor == j:
                return weight
        return None


if __name__ == '__main__':
    # 图的邻接矩阵表示
    adjacent_list = {
        0: [(1, 5), (2, 2)],
        1: [(3, 1), (4, 6)],
        2: [(3, 6), (5, 8)],
        3: [(4, 1), (5, 2)],
        4: [(6, 7)],
        5: [(6, 3)],
        6: []
    }
    dfs = DFS(adjacent_list)
    print(dfs.run(source=0, target=6))

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

深度优先搜索图时，可以使用栈，效率更高。此外，不必遍历完所有路径再计算路径距离选出最短路，每次回溯时，若当前距离比已找到的路径距离更长，即可提前结束本次搜索。

Floyd算法（Floyd-Warshell算法）

应用场景：多源最短路径算法（即一次性计算出所有点之间相互的最短距离），适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（可以处理有负权边的情况，但无法处理负权环）
其思想是：两点之间的最短路径，要么是这两点直接相连，要么是通过某一点中转。如i到j点间的最短路，要么是i和j直接直接相连，要么通过i->k->j。因此floyd算法通过两个矩阵，distance记录任意两点之间的最短距离，sequence矩阵记录两点之间的中转点。对于任意的两点i和j，检查通过其他所有的点k,（ $\in V -\{i,j\}$ ），是否距离更短，即若distance[i][k]+distance[k][j]<distance[i][j]，则更新distance[i][j]=distance[i][k]+distance[k][j]，并记录sequence[i][j]=k。
时间复杂度： $O(V^3)$ （三层for循环）

import collections
import numpy as np


def floyd_warshall(adjacent_list, source=0, target=6):
    node_list = adjacent_list.keys()
    distance = np.empty(shape=(len(node_list), len(node_list)), )
    sequence = collections.defaultdict(int)
    distance.fill(np.inf)
    for i in range(distance.shape[0]):
        distance[i][i] = 0

    for i, j_weight_list in adjacent_list.items():
        for j, weight in j_weight_list:
            distance[i][j] = weight

    for i in node_list:
        for j in node_list:
            for k in node_list:
                if distance[i][k] + distance[k][j] < distance[i][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    sequence[i, j] = k
    print(distance)
    print(sequence)

    path = [target]
    mid = sequence.get((source, target))
    path.append(mid)
    while True:
        mid = sequence.get((source, mid), source)
        path.append(mid)
        if mid == source:
            break
    path.reverse()
    return path


if __name__ == '__main__':
    # 图的邻接矩阵表示
    adjacent_list = {
        0: [(1, 5), (2, 2)],
        1: [(3, 1), (4, 6)],
        2: [(3, 6), (5, 8)],
        3: [(4, 1), (5, 2)],
        4: [(6, 7)],
        5: [(6, 3)],
        6: []
    }
    print(floyd_warshall(adjacent_list, source=0, target=6))

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

Dijkstra算法

应用场景：单源最短路径算法（只能计算出某个点到其他点的最短距离），无法处理存在负权边的情况，不能求含负权边的图
算法思想：用两个集合，永久标号集合P和临时标号集合T，P的作用是记录已求出最短路径的顶点（以及相应的最短路径长度），而T则是记录还未求出最短路径的顶点（以及该顶点到起点V_0的距离）。初始化将所有顶点加入T集合，从T集合中获取最小标号的顶点vi（一开始是v0），将vi加入P集合。每次迭代查找vi的邻接点vj，更新T集合vj的距离（ $v_j=v_i+d_{ij}$ ），当T集合为空时，所有顶点都被永久标号，算法结束。

注：每次从T集合中取出最小标号的顶点，是有优先级的，即标号最小的优先弹出，因此可以使用优先队列，进一步可以使用斐波那契堆进行优化。

时间复杂度：
- 用数组来储存每个节点 $\text O(V^2)$
- 一个普通优先级队列 $\text O((V+E)\lg V)$
- 用斐波那契堆实现的优先级队列 $\text O(V\lg V+E)$

import numpy as np

inf = np.inf


def dijkstra(graph, source, target):
    permanent = {source: 0}  # 永久标号，记录了每个点的最短距离
    temporary = {}  # 临时标号
    sequence = {}  # 记录每个顶点的最优前驱节点，用于记录最短路
    nodes = graph.keys()  # 顶点集合

    # 初始化
    for node in nodes:
        if node != source:
            temporary[node] = inf

    current_node = source

    while temporary:  # 若临时标号集合不为空，算法继续
        neighbor_weight_list = graph[current_node]
        for n, w in neighbor_weight_list:
            if permanent[current_node] + w < temporary[n]:
                temporary[n] = permanent[current_node] + w
                sequence[n] = current_node

        min_key = None
        min_val = 1e6
        for k, v in temporary.items():
            if v < min_val:
                min_val = v
                min_key = k
        temporary.pop(min_key)

        permanent[min_key] = min_val
        current_node = min_key

    # 从sequence中获取最短路
    current = target
    path = [target]
    while True:
        mid = sequence[current]
        path.append(mid)
        current = mid
        if mid == source: break
    path.reverse()
    # 返回最短路及距离
    return path, permanent[target]


if __name__ == "__main__":
    # 有向图的邻接表，点：【（临界点，权值），（邻接点，权值）】
    graph = {
        0: [(1, 5), (2, 2)],
        1: [(3, 1), (4, 6)],
        2: [(3, 6), (5, 8)],
        3: [(4, 1), (5, 2)],
        4: [(6, 7)],
        5: [(6, 3)],
        6: []
    }
    # 打印最短路径
    print(dijkstra(graph, 0, 6))
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
51
52
53
54
55
56
57
58
59
60
61
62

输出结果为：

([0, 1, 3, 5, 6], 11)
1

A*算法

Dijkstra算法和Floyd算法均为动态规划算法且是一种贪心算法，即进行无方向性的搜索，每一步转移都由计算机选择当前的最优解并生成新的状态，一直到达目标状态为止。由于其满足最优子结构性质，因此求出的最短路径序列的子序列也是最短路径，能够保证解为全局最优解。但当节点数量过大的时候，计算量也是无法接受的，由此诞生了A*算法。

基于A*的最短路径问题求解

贝尔曼福特算法（Bellman-Ford Algorithm）

应用场景：单源最短路算法，不能处理含负权环的情况
时间复杂度： $\text O(VE)$ ，显然不如dijkstra快

算法步骤：
输入：图和起点source
输出：从source到其他所有顶点的最短距离。【注】如果有负权回路，则不计算该最短距离，没有意义，因为可以穿越负权回路任意次，则最终为负无穷。

step1. 初始化：source到自身的距离=0，到其他顶点的距离为正无穷 $dist[v]←\inf, dist[s]←0$
step2. 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行 $∣ V ∣ - 1$ 次，因为以source为起点的树的最大深度为 $∣ V ∣ - 1$ ）
【注】松弛操作：对于边（i，j）起点到j的距离>起点到i的距离+边（i，j）的权重，则更新起点到j的距离。
```
# 松弛操作：
if distance[to_node] > distance[from_node] + weight:
    distance[to_node] = distance[from_node] + weight
1
2
3
```
step3. 检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 dist[v]中。

import numpy as np


def bellman_ford(adjacent_list, source, target):
    node_list = adjacent_list.keys()
    edge_weight = {}
    sequence = {}

    for i, j_weight_list in adjacent_list.items():
        for j, weight in j_weight_list:
            edge_weight[i, j] = weight

    distance = [0 if v == source else np.inf for v in node_list]  # 记录起点-所有点的最短距离
    for v in range(len(node_list) - 1):
        for (from_node, to_node), weight in edge_weight.items():
            if distance[to_node] > distance[from_node] + weight:
                distance[to_node] = distance[from_node] + weight
                sequence[to_node] = from_node

    # 从sequence中获取最短路
    current = target
    path = [target]
    while True:
        mid = sequence[current]
        path.append(mid)
        current = mid
        if mid == source: break
    path.reverse()
    # 返回最短路及距离
    return path, distance[target]


if __name__ == '__main__':
    # 图的邻接矩阵表示
    adjacent_list = {
        0: [(1, 5), (2, 2)],
        1: [(3, 1), (4, 6)],
        2: [(3, 6), (5, 8)],
        3: [(4, 1), (5, 2)],
        4: [(6, 7)],
        5: [(6, 3)],
        6: []
    }

    print(bellman_ford(adjacent_list, source=0, target=6))
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

([0, 1, 3, 5, 6], 11)
1

参考：

SPFA算法（Shortest Path Faster Algorithm）

Bellman—Ford算法的队列优化还有一个名字叫做SPFA。

算法应用场景

确定起点的最短路径问题：即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。
确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题：即已知起点和终点，求两点之间的最短路径。
全局最短路径问题：求图中所有的最短路径。适合使用Floyd-Warshall算法。

二、k最短路径问题（K-Shortest Path Problem）

因为应用场景的多样性和复杂性，在路径规划问题中，业务人员不仅想要知道最短路径，还想知道次短路径。比如在地图导航应用中，用户往往想获取最短的几种行程方案，也许耗时最短的方案可能价格昂贵，或者需要用户进行多次换乘，而次短的方案可能更实惠，或者可以直达目的地，提供多条最优线路可以让用户能够根据自己额外的需求(比如时间、费用和舒适度)来做出权衡和决策。

基于这样的应用场景，1959年，Hoffman和Pavley首次提出了K-最短路问题，多年来一直受到业界的广泛关注，虽然现在已经出现了不少求解算法，但还没有一个算法像Dijkstra最短路算法那样得到广泛的认可。一个原因是因为应用场景的多样性和复杂性，还没有什么通用的K-最短路算法在所有场景下都表现良好，因此K-最短路算法仍有很大的优化空间。

基于Yen算法的k最短路径问题

Jin Y.Yen在1971年发表了求解K-最短路问题的Yen算法，Yen算法以Dijkstra算法为基础，采用了递推法中的偏离路径的算法思想来逐一求解前K条最短路，适用于计算非负权边的有向无环图中的单源K-最短路。networkx中Yen算法使用如下：

import networkx

def find_k_shortest_paths(source, target, k=3):
    return list(islice(networkx.shortest_simple_paths(graph, source, target), k))
1
2
3
4

Yen算法的优点是易于理解，可以准确地找到图中任意两节点间的k条最短路径，缺点是时间复杂度较高，时间代价较大，主要原因是在求 $P_{i+1}$ 时，要将 $P_i$ 上除了终止节点外的所有节点都视为偏离节点，从而在选择偏离节点发展候选路径时占用了大量的时间。

为提高运行速度，后人在此算法的基础上不断改进和发展。比较有效的算法之一是马丁斯（Martins）在1999年提出的MPS算法，其特点是简化了偏离路径的长度计算，在生成候选边时不像Yen算法那样计算每条候选路径的长度，而是要求更新每条弧上的减少长度，只选择长度减少最小的弧作为最短偏离路径，该算法在一般情况下可以提高运行速度，但是在最差的情况下与Yen算法的时间复杂度一样。

三、Networkx中最短路算法使用

导入networkx库

import matplotlib.pyplot as plt
import networkx
1
2

数据准备

# 图的邻接矩阵表示
graph_adjacent_list = {
        0: [(1, 5), (2, 2)],
        1: [(3, 1), (4, 6)],
        2: [(3, 6), (5, 8)],
        3: [(4, 1), (5, 2)],
        4: [(6, 7)],
        5: [(6, 3)],
        6: []
}
# 节点及坐标
node_coordinate = {
        0: (0, 3),
        1: (1.5, 1.5),
        2: (2, 4),
        3: (3.5, 3),
        4: (4.5, 1),
        5: (4.5, 4.5),
        6: (6.5, 3)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

创建有向图

# 创建有向图
graph = networkx.DiGraph()
# 添加节点到graph
graph.add_nodes_from(graph_adjacent_list.keys())
# 添加边和权重到graph
src_tgt_weight_list = [(src, tgt, weight) for src, tgt_weight_list in graph_adjacent_list.items() for tgt, weight in tgt_weight_list]
graph.add_weighted_edges_from(src_tgt_weight_list)
1
2
3
4
5
6
7

# 图形可视化
networkx.draw_networkx(graph, pos=node_coordinate, with_labels=True, alpha=1, )
1
2

Floyd算法（Floyd-Warshell算法）,Floyd算法, 返回每个点到其他所有点的最短距离

for k, v in networkx.floyd_warshall(graph, weight="weight").items():
    print(k, v)
1
2

0 defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000001DFB3772AC0>, {0: 0, 1: 5, 2: 2, 3: 6, 4: 7, 5: 8, 6: 11})
1 defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000001DFB3FF8E00>, {1: 0, 3: 1, 4: 2, 0: inf, 2: inf, 5: 3, 6: 6})
2 defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000001DFB3FF8F40>, {2: 0, 3: 6, 5: 8, 0: inf, 1: inf, 4: 7, 6: 11})
3 defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000001DFB3FF9080>, {3: 0, 4: 1, 5: 2, 0: inf, 1: inf, 2: inf, 6: 5})
4 defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000001DFB3FF91C0>, {4: 0, 6: 7, 0: inf, 1: inf, 2: inf, 3: inf, 5: inf})
5 defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000001DFB3FF9300>, {5: 0, 6: 3, 0: inf, 1: inf, 2: inf, 3: inf, 4: inf})
6 defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000001DFB3FF93A0>, {6: 0, 0: inf, 1: inf, 2: inf, 3: inf, 4: inf, 5: inf})
1
2
3
4
5
6
7

#  使用networkx中的dijkstra算法，查找最短路径
networkx.dijkstra_path(graph, source=0, target=6, weight='weight')
1
2

[0, 1, 3, 5, 6]
1

# 使用networkx中的bellman-ford算法，查找最短路径
networkx.bellman_ford_path(graph, source=0, target=6, weight='weight')
1
2

[0, 1, 3, 5, 6]
1

# A*算法
networkx.astar_path(graph, source=0, target=6, weight='weight')
1
2

[0, 1, 3, 5, 6]
1

# shortest_path()方法查找最短路径，可以选择dijkstra（默认）和 bellman-ford
print(networkx.shortest_path(graph, source=0, target=6, weight='weight', method='dijkstra'))
1
2

[0, 1, 3, 5, 6]
1

# 查找起点-终点的所有路径，距离依次递增
list(networkx.shortest_simple_paths(graph, source=0, target=6, weight='weight'))
1
2

[[0, 1, 3, 5, 6],
 [0, 2, 5, 6],
 [0, 2, 3, 5, 6],
 [0, 1, 3, 4, 6],
 [0, 2, 3, 4, 6],
 [0, 1, 4, 6]]
1
2
3
4
5
6

单源最短路算法

计算给定起点-其他所有点的最短路径

# 使用dijkstra算法，计算给定起点-其他所有点的最短路径
networkx.single_source_dijkstra_path(graph, source=0, weight="weight")
1
2

{0: [0],
 1: [0, 1],
 2: [0, 2],
 3: [0, 1, 3],
 5: [0, 1, 3, 5],
 4: [0, 1, 3, 4],
 6: [0, 1, 3, 5, 6]}
1
2
3
4
5
6
7

# 使用bellman-ford算法，计算给定起点-其他所有点的最短路径
networkx.single_source_bellman_ford_path(graph, source=0, weight="weight")
1
2

{0: [0],
 1: [0, 1],
 2: [0, 2],
 3: [0, 1, 3],
 4: [0, 1, 3, 4],
 5: [0, 1, 3, 5],
 6: [0, 1, 3, 5, 6]}
1
2
3
4
5
6
7

若要在计算起点-终点的最短路径的同时获得距离，networkx可采用的方法有
single_source_dijkstra(G, source, target=None, cutoff=None, weight="weight")和single_source_bellman_ford(G, source, target=None, weight="weight")，若指定起点和终点，则计算起点-终点的最短路径及距离；若指定起点，不指定终点，则计算起点-所有其他点的最短路径及距离。

# 使用single_source_dijkstra(), 计算给定起点-终点的最短路径及距离
networkx.single_source_dijkstra(graph, source=0, target=6, weight='weight')
1
2

(11, [0, 1, 3, 5, 6])
1

# 返回起点-终点的最短路径及距离
networkx.single_source_bellman_ford(graph, source=0, target=6, weight='weight')
1
2

(11, [0, 1, 3, 5, 6])
1

# 使用single_source_dijkstra(), 计算给定起点-所有其他点的最短路径及距离
networkx.single_source_dijkstra(graph, source=0, target=None, weight='weight')
1
2

({0: 0, 2: 2, 1: 5, 3: 6, 4: 7, 5: 8, 6: 11},
 {0: [0],
  1: [0, 1],
  2: [0, 2],
  3: [0, 1, 3],
  5: [0, 1, 3, 5],
  4: [0, 1, 3, 4],
  6: [0, 1, 3, 5, 6]})
1
2
3
4
5
6
7
8

# 使用single_source_bellman_ford(), 计算给定起点-所有其他点的最短路径及距离
networkx.single_source_bellman_ford(graph, source=0, target=None, weight='weight')
1
2

({0: 0, 1: 5, 2: 2, 3: 6, 4: 7, 5: 8, 6: 11},
 {0: [0],
  1: [0, 1],
  2: [0, 2],
  3: [0, 1, 3],
  4: [0, 1, 3, 4],
  5: [0, 1, 3, 5],
  6: [0, 1, 3, 5, 6]})
1
2
3
4
5
6
7
8

# 返回起点-终点的最短路（无权）
networkx.bidirectional_shortest_path(graph, source=0, target=6)
1
2

[0, 1, 4, 6]
1

搜索起点-终点间的所有路径：shortest_simple_paths(G, source, target, weight=None)

list(networkx.shortest_simple_paths(graph, source=0, target=6, weight="weight"))
1

[[0, 1, 3, 5, 6],
[0, 2, 5, 6],
[0, 2, 3, 5, 6],
[0, 1, 3, 4, 6],
[0, 2, 3, 4, 6],
[0, 1, 4, 6]]
1
2
3
4
5
6

返回结果为所有路径，第一个为最短路径。该方法shortest_simple_paths基于Yen’s Algorithm，

Jin Y. Yen, “Finding the K Shortest Loopless Paths in a Network”, Management Science, Vol. 17, No. 11, Theory Series (Jul., 1971), pp. 712-716.

如果搜索前k短路径，时间复杂度为 $O(kV^3)$ ：

from itertools import islice
def k_shortest_paths(G, source, target, k, weight="weight"):
    return list(
        islice(networkx.shortest_simple_paths(graph, source, target, weight=weight), k)
    )
for path in k_shortest_paths(graph, 0, 6, k=3):
    print(path)
1
2
3
4
5
6
7

[0, 1, 3, 5, 6]
[0, 2, 5, 6]
[0, 2, 3, 5, 6]
1
2
3

参考

深度优先算法详解
https://blog.csdn.net/weixin_44267007/article/details/119770562
https://blog.csdn.net/qq_40347399/article/details/119879750
https://blog.csdn.net/wzy_2017/article/details/78910697

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/791588