图与网络——最短路问题精解

标签：短路 路径 网络 算法 path INF 精解 节点

最短路问题（Shortest Path Problem）是图论中的一个经典问题，广泛应用于现实世界中的多个领域。该问题的核心在于如何在一个图中找到给定起点和终点之间路径权重最小的路径。路径权重通常代表时间、成本、距离等因素，因此最短路问题不仅具有理论上的研究价值，还在实际问题的解决中发挥了重要作用，如管路铺设、线路安装、交通规划等领域。

一、最短路问题概述

1.1 最短路问题的界定

在最短路问题中，图的每一条边都赋予一个权重，通常表示距离、成本、时间或其他与问题相关的度量标准。给定一个图和两点，最短路问题的目标是找到两点之间经过的路径，使得沿路径的边权重之和最小。根据问题的具体形式，最短路问题可以分为不同的类型。

单源最短路问题：这是经典的、单源的、标准的最短路问题，目标是给定一个起点，找到从该起点到图中其他所有点的最短路径。常见的算法包括Dijkstra算法、Bellman-Ford算法等。
给定起点的最短路径问题：即从一个固定的起点出发，求出从该起点到图中其他所有节点的最短路径。这类问题在很多场景下都有应用，如在交通运输中规划从一个城市出发到其他城市的最短路线。
给定终点的最短路径问题：这是给定终点情况下的最短路径问题。在无向图中，这与给定起点问题相同，而在有向图中则需要将路径的方向进行逆转。这类问题也可以通过修改Dijkstra算法来解决。
全局最短路问题：多源最短路问题，即任意两点之间的最短路径问题。求解这一问题需要找到图中每对点之间的最短路径。常见的算法包括Floyd-Warshall算法和Johnson算法。全局最短路问题的典型应用是在交通管理系统中，计算城市路网中任意两个点之间的最短时间或最短距离。

给定一个网络图 \(D=(V, A, W)\)，记 \(D\) 中每一条弧 \(a_{ij}=(v_i, v_j)\) 上的权为 \(w(a_{ij})=w_{ij}\)。指定 \(D\) 的起点 \(v_s\) 和终点 \(v_t\)，设 \(P\) 是 \(D\) 中从 \(v_s\) 到 \(v_t\) 的一条路，则定义路 \(P\) 的权是 \(P\) 中所有弧的权之和，记为 \(w(P)\)，即：

\[w(P) = \sum_{(v_i, v_j)} w_{ij} \]

若 \(P^*\) 是 \(D\) 中 \(v_s\) 到 \(v_t\) 的一条路，且满足：

\[w(P^*) = \min\{w(P) \mid P是 v_s到 v_t的路\} \]

其中，min 表示对 \(D\) 的所有从 \(v_s\) 到 \(v_t\) 的路 \(P\) 的权取最小，则称 \(P^*\) 为从 \(v_s\) 到 \(v_t\) 的最短路，\(w(P^*)\) 为从 \(v_s\) 到 \(v_t\) 的最短距离。
在一个图 \(D=(V, A, W)\) 中，求从 \(v_s\) 到 \(v_t\) 的最短路或最短距离的问题称为最短路问题，这即时经典的、单源的、标准的最短路问题。

1.2最短路问题的应用

城市网络管理：最短路问题在城市交通网络中的应用非常广泛。现代城市交通系统复杂多样，不仅要考虑道路的长度，还需要综合考虑实时交通状况、路面拥堵等问题。在城市网络中，每条道路可以被赋予时间权重，时间权重表示车辆在该道路上行驶的时间。利用最短路算法，可以计算出车辆从一个地点到达目的地所需的最短时间路线，进而为交通管理系统提供优化的行车路线规划。例如，许多导航应用程序（如Google地图、高德地图等）实时获取交通数据，根据不同路段的拥堵情况更新道路权重，计算出当前情况下驾驶时间最短的路线。这些应用通过最短路算法快速响应，并为驾驶者提供最优的行驶路线，减少交通拥堵的影响，提高道路的利用率。
舰船通道设计：图论及最短路径问题在舰船通道优化设计中也得到了应用。在舰艇的多层甲板结构中，人员的通行效率至关重要，尤其是在紧急情况下，人员必须快速而有序地撤离。为此，设计合理的通道路线显得尤为重要。在舰船通道设计中，每一段通道（包括楼梯）都可以看作图中的边，而每条边的权重代表了人员通过该段通道所需的时间。该时间可以根据人员流动速度和通道拥堵情况来估算。通过建立舰船的通道网络图，并以行程时间为通道网络的路权，设计者可以利用最短路算法来计算出从任何起点到终点的最短撤离路径。这种方法在舰艇设计中可以确保人员的快速、安全撤离，提高通行效率，减少不必要的延误。
其他应用领域：最短路问题在很多其他领域也有广泛的应用。例如，在物流配送中，最短路问题用于寻找最优的配送路线，以降低运输成本和时间；在互联网路由协议中，最短路算法被用于寻找数据包从源节点到目的节点的最优传输路径；在社交网络分析中，最短路径算法可用于衡量网络中两个节点之间的距离，帮助研究人员发现用户之间的潜在联系。

二、最短路问题的Python实现

最短路问题有多种经典的算法来解决：Dijkstra算法：用于解决非负权重的单源最短路径问题。该算法以贪心的思想为基础，逐步扩展最短路径，直到找到所有点的最短路径。Bellman-Ford算法：可解决带有负权边的单源最短路径问题，能够处理负权回路。Floyd-Warshall算法：用于解决全局最短路径问题，能够找出任意两点之间的最短路径，时间复杂度较高，适用于小规模图。Johnson算法：通过重新标定图中的边权，能够高效地解决大规模图的全局最短路径问题。

Dijkstra算法	Floyd算法

2.1 Dijkstra算法

Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Bellman最优化原理
若 \(P\) 是网络图 \(D\) 中从 \(v_s\) 到 \(v_t\) 的一条最短路，\(v_1\) 是 \(P\) 中除 \(v_s\) 与 \(v_t\) 外的任意一个中间点，则沿 \(P\) 从 \(v_s\) 到 \(v_1\) 的路 \(P_1\) 也是 \(v_s\) 到 \(v_1\) 的最短路。

在上图中，从 \(v_s\) 到 \(v_t\) 有三条路:\(v_s \rightarrow v_2 \rightarrow v_1 \rightarrow v_t\) （路权 9）；\(v_s \rightarrow v_3 \rightarrow v_1 \rightarrow v_t\) （路权 13）；\(v_s \rightarrow v_1 \rightarrow v_t\) （路权 10）。因为 \(v_s\) 到 \(v_t\) 最短路是 \(v_s \rightarrow v_2 \rightarrow v_1 \rightarrow v_t\)，所以 \(v_s \rightarrow v_2 \rightarrow v_1\) 也是 \(v_s\) 到 \(v_1\) 的最短路。

就得如下求解思路:

• 为求得 \(v_s\) 到 \(v_t\) 的最短路，可先求得 \(v_s\) 到中间点的最短路，然后由中间点再逐步过渡到终点 \(v_t\)。
• 在计算过程中，需要把顶点集 \(V\) 中“经判断为最短路 \(P\) 途经之点 \(i\)”和“尚未判断是否为最短路 \(P\) 途经之点 \(j\)”区分开来，为此可设置集合 \(I\) 和 \(J\)，前者归入 \(I\)，后者归入 \(J\)。
• 为区分中间点 \(v_i\) 是否已归入 \(I\) 中以及逆向追踪的便利，可在归入 \(I\) 中的点 \(v_i\) 给予双标号 \(\left(v_k, l_i\right)\)，此中 \(l_i\) 表示从 \(v_s\) 到 \(v_i\) 最短路的距离，而 \(v_k\) 则为从 \(v_s\) 到 \(v_i\) 最短路 \(P\) 中 \(v_i\) 的前一途经节点。

算法步骤
设图为 \(G(V,E)\), V为点集, E为边集, 其中, 对于 \(\forall i,j\in V,\,c_{ij}\) 为从点i到点j的距离，\(d_i,\forall i\in V-\{s\}\) 表示从s出发到达i的最短距离。

• 初始时令 \(S=s,\,T=V-S=\{\) 其余顶点 \(\},\,T\) 中顶点对应的距离值若存在 \(<s, V_i>\), 则 \(d_{V_i}\) 为 \(<s,V_i>\) 弧上的权值，若不存在 \(<s,V_i>\), 则 \(d_{V_i}\) 为 + \(\infty\)。
• 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中。
• 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从s到 \(V_i\) 的距离值缩短，则修改此距离值，即存在 \(d_{V_i}>d_w+c_{V_i,w}\)，其中 \(V_i\in S,\,w\in T\) 时，更新 \(d_{V_i}\leftarrow d_w+c_{V_i,w}\)。重复上述步骤2、3，直到S中包含所有顶点，即 \(W=V_i\) 为止。

例1：求下面网络图的\(v_1\)到\(v_6\)最短路

import networkx as nx
import matplotlib.pyplot as plt
import heapq
import warnings

# 忽略DeprecationWarning警告
warnings.filterwarnings("ignore", category=DeprecationWarning)

# Dijkstra算法实现
def dijkstra(graph, start, end):
    queue = [(0, start, [])]
    visited = set()  # 用于记录已访问的节点

    while queue:
        (cost, node, path) = heapq.heappop(queue)

        if node in visited:
            continue

        visited.add(node)
        path = path + [node]

        if node == end:
            return (cost, path)

        for (adjacent, weight) in graph.get(node, []):
            if adjacent not in visited:
                heapq.heappush(queue, (cost + weight, adjacent, path))

    return float("inf"), []  # 如果无可行路径，返回无穷大和空路径

# 定义图结构 (邻接表)
graph = {
    1: [(6, 1), (4, 3)],
    2: [(4, 2), (7, 1)],
    3: [(4, 3), (7, 3), (5, 4)],
    4: [(1, 3), (2, 2), (3, 3)],
    5: [(3, 4), (6, 3), (7, 5)],
    6: [(1, 1), (5, 3)],
    7: [(2, 1), (3, 3), (5, 5)]
}

# 使用Dijkstra算法找到从1到7的最短路径
distance, shortest_path = dijkstra(graph, 1, 7)

# 输出最短路径和距离
print(f"从节点 1 到节点 7 的最短路径为: {shortest_path}, 距离为: {distance}")

# 可视化图形
G = nx.Graph()

# 添加图的边
edges = [
    (1, 6, 1), (1, 4, 3), (2, 4, 2), (2, 7, 1),
    (3, 4, 3), (3, 7, 3), (3, 5, 4), (4, 1, 3),
    (5, 3, 4), (5, 6, 3), (5, 7, 5), (6, 1, 1),
    (7, 2, 1), (7, 3, 3), (7, 5, 5)
]

# 将边添加到图中
for edge in edges:
    G.add_edge(edge[0], edge[1], weight=edge[2])

# 设置节点位置
pos = {1: (2, 2), 2: (0, 3), 3: (2, 1), 4: (1, 2.5), 
       5: (3, 1), 6: (3, 2), 7: (0, 1)}

# 获取边权重
edge_labels = {(u, v): f'{d["weight"]}' for u, v, d in G.edges(data=True)}

# 绘制节点和边
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=3000, font_size=48, font_weight='bold')

# 绘制边权重并调整字体大小
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=36)

# 高亮显示最短路径
path_edges = [(shortest_path[i], shortest_path[i+1]) for i in range(len(shortest_path)-1)]
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=9)  # 线条宽度设为原来的三倍

# 显示图形
plt.title("Graph Representation with Shortest Path Highlighted", fontsize=36)
plt.show()

Dijkstra算法利用的是贪心的思想，来求解最短路，所以Dijkstra的求解速度很快，时间复杂度是 \(O(|V|^2)\)，如果使用堆优化可以将复杂度优化到 \(O(|V|+|E|log|E|)\) (当然如果有一些例如斐波那契堆，可以更优化，有兴趣的朋友可以自行查找)。但是Dijkstra算法只适合于不带负权边的算法，因此算法的局限性还是很大的。

2.2 Floyd算法

Floyd算法是一个基于贪心、动态规划来求一个图中所有点到所有点最短路径的算法，适用于带权有向图或无向图，可以处理负权边，但不能处理负权回路，时间复杂度为 \(O(n^3)\)。记$$D[i][j] = \min(D[i][j], D[i][k] + D[k][j])$$

• \(i, j\) 分别指行、列；
• \(k\) 指起点到终点途中除终点外的所有节点数；
• \(D[i][j]\) 表示从 \(i\) 节点到 \(j\) 节点的最短路径；
• \(D[i][k]\) 表示从 \(i\) 节点到 \(k\) 节点的最短路径；
• \(D[k][j]\) 表示从 \(k\) 节点到 \(j\) 节点的最短路径。

通过上式规则，逐步引入中间节点 \(k\) 的信息来改进从 \(i\) 到 \(j\) 的最短路径估计。

算法流程

• 初始化：首先初始化图中的邻接矩阵，\(D[i][j]\) 初始化为图中 \(i\) 到 \(j\) 的边权，如果 \(i\) 和 \(j\) 之间没有直接边，则设置为无穷大 \((\infty)\)，自环的距离为 0。
• 更新距离矩阵：使用三重循环遍历所有顶点对和中间点来更新距离矩阵。在此过程中主要思想是对于每对顶点 \((i, j)\)，检查是否通过某个中间点 \(k\) 可以找到更短的路径。
• 检测负权回路：Floyd算法可以检测负权回路（即从某个顶点出发经过若干条边后回到该顶点的总权重为负），但无法处理负权回路。在完成所有的更新后，检查对角线元素 \(D[i][i]\) 是否小于 0。如果小于 0 则表示存在负权回路。

例2：求下面网络图的全局最短路

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

# Floyd-Warshall算法实现
def floyd_warshall(graph):
    num_vertices = len(graph)
    dist = np.copy(graph)  # 距离矩阵初始化为输入的图
    next_vertex = np.zeros((num_vertices, num_vertices), dtype=int)  # 保存路径中继点

    # 初始化路径
    for i in range(num_vertices):
        for j in range(num_vertices):
            if graph[i][j] != float('inf') and i != j:
                next_vertex[i][j] = j + 1  # 节点从1开始

    # Floyd-Warshall核心算法
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_vertex[i][j] = next_vertex[i][k]

    return dist, next_vertex

# 构建邻接矩阵（根据图像）
INF = float('inf')
graph = [
    [0, INF, INF, 3, INF, 1, INF],  # 1号节点
    [INF, 0, INF, 2, INF, INF, 1],  # 2号节点
    [INF, INF, 0, 3, 4, INF, 3],    # 3号节点
    [3, 2, 3, 0, INF, INF, INF],    # 4号节点
    [INF, INF, 4, INF, 0, 3, 5],    # 5号节点
    [1, INF, INF, INF, 3, 0, INF],  # 6号节点
    [INF, 1, 3, INF, 5, INF, 0]     # 7号节点
]

# 运行Floyd-Warshall算法
dist_matrix, path_matrix = floyd_warshall(graph)

# 打印所有节点对的最短路径和距离（以矩阵形式输出）
def print_shortest_path_matrix(dist_matrix):
    print("最短路径距离矩阵：")
    print(np.array(dist_matrix))

# 打印最短路径矩阵
print_shortest_path_matrix(dist_matrix)

最短路径距离矩阵：
[[0. 5. 6. 3. 4. 1. 6.]
 [5. 0. 4. 2. 6. 6. 1.]
 [6. 4. 0. 3. 4. 7. 3.]
 [3. 2. 3. 0. 7. 4. 3.]
 [4. 6. 4. 7. 0. 3. 5.]
 [1. 6. 7. 4. 3. 0. 7.]
 [6. 1. 3. 3. 5. 7. 0.]]

三、最长路问题的Python实现

import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict

# 创建图类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点的数量
        self.graph = defaultdict(list)  # 默认字典，用于存储图

    # 添加边到图中
    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))

    # 拓扑排序函数
    def topological_sort_util(self, v, visited, stack):
        visited[v] = True
        if v in self.graph:
            for node, weight in self.graph[v]:
                if not visited[node]:
                    self.topological_sort_util(node, visited, stack)
        stack.append(v)

    # 获取DAG中从给定起点到终点的最长路径
    def longest_path(self, s, t):
        # 初始化
        visited = [False] * self.V
        stack = []

        # 拓扑排序
        for i in range(self.V):
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)

        # 初始化距离数组，起点距离为0，其它为负无穷
        dist = [-float('inf')] * self.V
        dist[s] = 0

        # 初始化路径字典来跟踪路径
        path = {i: [] for i in range(self.V)}
        path[s] = [s]

        # 处理拓扑排序
        while stack:
            i = stack.pop()
            if dist[i] != -float('inf'):
                for node, weight in self.graph[i]:
                    if dist[node] < dist[i] + weight:
                        dist[node] = dist[i] + weight
                        # 更新路径信息
                        path[node] = path[i] + [node]

        # 如果终点不可达
        if dist[t] == -float('inf'):
            print(f"从顶点 {s} 到顶点 {t} 不可达")
        else:
            # 打印从s到t的最长路径及其距离
            print(f"从顶点 {s} 到顶点 {t} 的最长路径为: {' -> '.join(map(str, path[t]))}")
            print(f"路径长度为: {dist[t]}")
        return dist, path

    # 绘制图形
    def draw_graph(self):
        G = nx.DiGraph()

        # 添加有向边及权重
        for u in self.graph:
            for v, weight in self.graph[u]:
                G.add_edge(u, v, weight=weight)

        # 设置布局和绘制参数，调整 k 参数拉开节点
        pos = nx.spring_layout(G, k=1.2)  # 调整 k 参数，k 值越大节点距离越远
        plt.figure(figsize=(8, 6))

        # 绘制节点和边
        nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=3000, font_size=12, font_weight='bold', arrows=True)
        nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{weight}' for u, v, weight in G.edges(data='weight')}, font_color='red')

        # 显示图形
        plt.title("有向无环图(DAG)与边权重")
        plt.show()

# 示例用法
g = Graph(5)  # 图中的5个节点 A, B, C, D, E
g.add_edge(0, 1, 3)  # A -> B, 权重3
g.add_edge(0, 2, 2)  # A -> C, 权重2
g.add_edge(1, 3, 1)  # B -> D, 权重1
g.add_edge(3, 0, 4)  # D -> A, 权重4
g.add_edge(3, 1, 1)  # D -> B, 权重1
g.add_edge(3, 2, 6)  # D -> C, 权重6
g.add_edge(3, 4, 4)  # D -> E, 权重4
g.add_edge(4, 2, 4)  # D -> C, 权重4

# 查找从顶点A(0)到顶点E(4)的最长路径
g.longest_path(0, 2)

# 绘制图形
g.draw_graph()

总结

最短路问题是图论中的核心问题之一，具有广泛的应用价值。其目标是在图中找到两点之间权重总和最小的路径，这些权重通常代表时间、成本或距离。最短路问题在多个领域发挥重要作用，例如，城市交通管理可以通过最短路径算法为车辆规划最优路线，减少交通拥堵；在物流配送中，最短路算法有助于找到运输成本最低的路线；在互联网网络路由中，最短路算法用于确定数据包的最佳传输路径。常见的最短路算法包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法等，针对不同问题和需求提供高效的解决方案。最短路问题通过这些算法在优化决策中发挥了关键作用，提升了效率和资源利用率。

参考资料

1. 最短路问题
2. 路径规划——Floyd算法

标签：短路,路径,网络,算法,path,INF,精解,节点
From： https://www.cnblogs.com/haohai9309/p/18407834