python实现Dijkstra算法求解最短路径问题（Shortest Path Problem）_最短路径算法dijkstra算法python

1. 最短路径问题

• 最短路问题（Shortest Path Problem，SPP）是图论的一个经典问题，其目的在于寻找网络中任意两个节点间的最短路径，这里的最短可以衍生为距离最短、费用最小、时间最短等一系列度量。当前的涌现了很多最短路径的变种，如带资源约束的最短路径问题（Shortest Path Problem with Resource Constraints, SPPRC）等；

• 数学模型
  m i n ∑ ( i , j ) ∈ A c i j x i j ∑ j ∈ V x i j − ∑ j ∈ V x j i = { − 1 , i = s 0 , i ≠ s a n d i ≠ t 1 , i = t min\sum_{(i,j)\in A}{c_{ij} x_{ij}}\\ \sum_{j \in V}x_{ij} - \sum_{j\in V}x_{ji} =

  $$\begin{cases} -1, & {i = s } \\ 0, & {i \neq s \quad and \quad i \neq t}\\ 1, & {i=t}\\ \end{cases}$$ min(i,j)∈A∑​cij​xij​j∈V∑​xij​−j∈V∑​xji​=⎩ ⎨ ⎧​−1,0,1,​i=si=sandi=ti=t​

  • $x_{ij}$: 0-1决策变量，$x_{ij}=1$表示经过弧$(i,j)$, $x_{ij}=0$表示不经过弧$(i,j)$

  • $c_{ij}$: 弧$(i,j)$上的权重

  • $A$: 所有弧的集合

  • $V$: 所有点的集合

  • $s,t$ :分别表示源节点和结束节点

2. 求解算法

一般使用label algorithm 或solver求解最短路径问题，本文使用Dijkstra algorithm和开源的SCIP求解器分别求解SPP, 并做结果对比。

2.1 Label Algorithm

• 标签算法是求解最短路径算法的常见算法，一般被分为两类：Label Setting Algorithm（如Dijkstra、Dial、Heap）和Label Correcting Algorithm(如Bellman-Ford、FIFO、Deque)，两者都是基于动态规划的思想，且都是精确性算法，得到解一定是最优解。
• 两者如何更新临时距离标签差异不同：Label Setting Algorithm，在每次迭代时将当前临时距离标签最小的更新为永久距离标签，直到所有的临时距离标签都更新为永久距离标签；而Label Correcting Algorithm在每次迭代时都有可能更新临时距离标签的值，直到最后一次迭代时所有的临时距离标签才成为永久距离标签；
• 以上的差异点导致标准Label Setting Algorithm不适用含有负环网络，如果网络中有负环，可以采用Label Correcting Algorithm，如Bellman-Ford算法求解；

2.1.1 Dijkstra algorithm

Dijkstra算法本质上结合了贪心算法 + 动态规划的思想，关于其理论部分就不在此赘述，详细算法步骤见代码注释

• Dijkstra算法是求一个特定起点到其他所有顶点的最短路径，也称为单源最短路径算法
• 算法时间复杂度一般是 $O(n^2)$
• Dijkstra algorithm由于属于Label Setting Algorithm，所以不适用含有负权网络

2.1.2 python代码实现Dijkstra算法

python实现Dijkstra两种方式:

1. 简洁一点，直接使用networkx提供了dijkstra算法的接口，只要定义带权重的图结构即可
2. 基于图结构，使用python实现算法步骤

两种方式python代码实现如下：

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import time
import pyscipopt as opt


def print_fun_run_time(func):
    def wrapper(*args, **kwargs):
        local_time = time.time()
        func(*args, **kwargs)
        print('current function [%s] run time is %.4f'%(func.__name__, time.time()-local_time))
    return wrapper


def pic_graph(Nodes, Arcs):
    """
    可视化图，节点的相对位置可能改变
    """
    np.random.seed(1)
    # 定义有向图
    Graph = nx.DiGraph()
    # 定义节点
    for node in Nodes:
        Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
    # 定义弧
    for (from_node, to_node), weight in Arcs.items():
        Graph.add_edge(from_node, to_node, weight=weight)

    plt.figure(figsize=(7, 5), dpi=100)
    pos = nx.spring_layout(Graph)

    nx.draw_networkx(Graph, pos)
    node_labels = nx.get_node_attributes(Graph, 'node_name')
    nx.draw_networkx_labels(Graph, pos, labels=node_labels)
    edge_labels = nx.get_edge_attributes(Graph, 'weight')
    nx.draw_networkx_edge_labels(Graph, pos, edge_labels=edge_labels)

    plt.savefig('./spp_grap.png')
    plt.show()

    return True


def prepare_data():
    # 测试数据: 邻接矩阵标识图结构，其中极大值1000表示不连通, 测试数据包含11个节点
    matrix = np.array([[0, 2, 8, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
                       [2, 0, 6, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000],
                       [8, 6, 0, 7, 5, 1, 2, 1000, 1000, 1000, 1000],
                       [1, 1000, 7, 0, 1000, 1000, 9, 1000, 1000, 1000, 1000],
                       [1000, 1, 5, 1000, 0, 3, 1000, 2, 1000, 1000, 1000],
                       [1000, 1000, 1, 1000, 3, 0, 4, 1000, 6, 1000, 1000],
                       [1000, 1000, 2, 9, 1000, 4, 0, 1000, 3, 1, 1000],
                       [1000, 1000, 1000, 1000, 2, 1000, 1000, 0, 7, 1000, 9],
                       [1000, 1000, 1000, 1000, 1000, 6, 3, 7, 0, 1, 2],
                       [1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1, 0, 4],
                       [1000, 1000, 1000, 1000, 1000, 1000, 1000, 9, 2, 4, 0]])

    # 转换数据（只是为了方便理解，不为效率）, 获取不包含本节点且连通的点及弧
    row, col = np.where((matrix != 1000) & (matrix != 0))
    Nodes = list(np.unique(np.unique(np.append(row, col)) + 1).astype('str'))
    Arcs = {}
    for i in range(len(row)):
        Arcs[str(row[i] + 1), str(col[i] + 1)] = matrix[row[i], col[i]]
    print('Nodes:\n', Nodes)
    print('Arcs:\n', Arcs)
    return Nodes, Arcs

@print_fun_run_time
def networkx_dijkstra(Nodes, Arcs, source, target):
    """
    networkx提供了dijkstra算法的方法的封装，只要定义图结构即可。感兴趣可以学一下networkx的源码。
    """
    Graph = nx.DiGraph()
    # 添加节点
    for node in Nodes:
        Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
    # 添加带权重的边
    for (from_node, to_node), weight in Arcs.items():
        Graph.add_weighted_edges_from([(from_node, to_node, weight)])

    path = nx.dijkstra_path(Graph, source=source, target=target)
    distance = nx.dijkstra_path_length(Graph, source=source, target=target)
    print(f'节点 {source} 到 {target} 的路径={path}, 最短距离={distance}')

    return True


@print_fun_run_time
def Dijkstra(Nodes, Arcs, source, target):
    """
    Parameters
    ----------
    Nodes: list
        the set of node

    Arcs: dict
        key: pairs of node (from node, end node)
        value: weight

    source : node
        Starting node

    target : node
        Ending node

    Returns
    -------
    path : list
        List of nodes in the shortest path
    distance: Float
        The short distance from source to target
    """
    # ========== 数据结构 ==========
    # 定义有向图
    Graph = nx.DiGraph()
    # 定义节点
    for node in Nodes:
        Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
    # 定义弧
    for (from_node, to_node), weight in Arcs.items():
        Graph.add_edge(from_node, to_node, weight=weight)

    # ========== 算法开始 ==========
    # 初始化未探索节点集合: 初始时为所有节点集合
    tmp_set = list(Graph.nodes())

    # 初始化当前节点及所有节点的最短距离：起始点作为当前节点，并将起始点的最短路径置为0，其他节点距离置为无穷大
    current_node = source
    for node in tmp_set:
        if (node == source):
            Graph.nodes[node]['min_dis'] = 0
        else:
            Graph.nodes[node]['min_dis'] = np.inf

    # 算法终止条件: 所有节点均被探索
    while (len(tmp_set) > 0):
        # 选择未探索的节点中的最短路径的节点作为新的当前节点
        min_dis = np.inf
        for node in tmp_set:
            if (Graph.nodes[node]['min_dis'] < min_dis):
                current_node = node
                min_dis = Graph.nodes[node]['min_dis']

        # 删除已探索的节点
        if (current_node != None):
            tmp_set.remove(current_node)

        """
        循环判断当前节点所有相邻的节点：
        1. 计算当前节点的最小值 + 相邻节点的权重的和，
        2. 若小于相邻节点的最小距离，则更新相邻节点的最小距离，并标记相邻节点的前一个节点为当前节点
        """
        for neighbor_node in Graph.successors(current_node):
            arc = (current_node, neighbor_node)
            dis_t = Graph.nodes[current_node]['min_dis'] + Graph.edges[arc]['weight']
            if (dis_t < Graph.nodes[neighbor_node]['min_dis']):
                Graph.nodes[neighbor_node]['min_dis'] = dis_t
                Graph.nodes[neighbor_node]['previous_node'] = current_node

    # ========== 获取结果 ==========
    """
    获取结果: 
    1. 结束节点上更新的最短距离即为整个最短路径的距离
    2. 根据结束节点回溯, 依次找到其上一个节点
    """
    distance = Graph.nodes[target]['min_dis']
    current_node = target
    path = [current_node]
    while (current_node != source):
        current_node = Graph.nodes[current_node]['previous_node']
        path.insert(0, current_node)

    print(f'节点 {source} 到 {target} 的路径={path}, 最短距离={distance}')
    return True


if __name__ == '__main__':
    source = '1'  # starting node
    target = '11'  # ending node
    # 测试数据
    Nodes, Arcs = prepare_data()
    # 可视化图
    pic_graph(Nodes, Arcs)
    # 方式1: 使用networkx提供了dijkstra算法的方法的封装
    networkx_dijkstra(Nodes, Arcs, source, target)
    # 方式2: python实现Dijkstra算法求解最短路径问题
    Dijkstra(Nodes, Arcs, source, target)
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

2.2 python调用SCIP求解器求解最短路径问题

代码实现可见之前写的博客 python调用求解器SCIP求解最短路径问题（Shortest Path Problem）

3. 算法结果

---

参考文献

Dijkstra E W . A Note on Two Problems in Connection with Graphs[J]. Numerische Mathematics, 1959.

Martins E . On a multicriteria shortest path problem[J]. European Journal of Operational Research, 1984, 16(2):236-245.