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

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

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

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

算法思想：
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点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))

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

Floyd算法（Floyd-Warshell算法）

多源最短路径算法（即一次性计算出所有点之间相互的最短距离），适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（可以处理有负权边的情况，但无法处理负权环）

其思想是：两点之间的最短路径，要么是这两点直接相连，要么是通过某一点中转。如i到j点间的最短路，要么是i和j直接直接相连，要么通过i->k->j。因此floyd算法通过两个矩阵，distance记录任意两点之间的最短距离，sequence矩阵记录两点之间的中转点。对于任意的两点i和j，检查通过其他所有的点k,（ k ∈ V ? { i , j } k \in V -\{i,j\} k∈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))

Dijkstra算法

单源最短路径算法（只能计算出某个点到其他点的最短距离），无法处理存在负权边的情况，不能求含负权边的图

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

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))

输出结果为：

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

A*算法

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

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

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

单源最短路算法，不能处理含负权环的情况

时间复杂度：$\text{O}(VE)$，显然不如dijkstra快

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

• step1. 初始化：source到自身的距离=0，到其他顶点的距离为正无穷$dist[v]\leftarrow \inf ,dist[s]\leftarrow 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
  

• 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))

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

参考：

• 算法系列——贝尔曼福特算法（Bellman-Ford）
• Bellman-ford 算法
• 【经典算法】Bellman-Ford最短路径算法

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))

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

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

• 付媛,朱礼军,韩红旗.K最短路径算法与应用分析[J].情报工程, 2015, 1(1):8.DOI:CNKI:SUN:QBGC.0.2015-01-018.
• K Shortest Path Routing
• networkx中shortest_simple_paths方法介绍
• networkX-04-查找k短路
  
• 前K条最短路径算法
  
• 最短路径分析之两点之间的k条最短路径
• 偏离点、偏离边及偏离路径介绍

三、Networkx中最短路算法使用

导入networkx库

import matplotlib.pyplot as plt
import networkx

数据准备

# 图的邻接矩阵表示
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)
}

创建有向图

# 创建有向图
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)

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

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

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

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})

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

[0, 1, 3, 5, 6]

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

[0, 1, 3, 5, 6]

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

[0, 1, 3, 5, 6]

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

[0, 1, 3, 5, 6]

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

[[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]]

单源最短路算法

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

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

{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]}

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

{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]}

若要在计算起点-终点的最短路径的同时获得距离，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')

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

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

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

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

({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]})

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

({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]})

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

[0, 1, 4, 6]

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

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

[[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]]

返回结果为所有路径，第一个为最短路径。该方法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(k{V}^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)

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

参考

• 深度优先算法详解
• 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