基于python的数学建模---图论模型（Dijkstra）

from collections import defaultdict

from heapq import *  # 堆--先进后出

inf = 99999  # 不连通值

mtx_graph = [[0, 1, inf, 3, inf, inf, inf, inf, inf],

             [1, 0, 5, inf, 2, inf, inf, inf, inf],

             [inf, inf, 0, 1, inf, 6, inf, inf, inf],

             [inf, inf, inf, 0, inf, 7, inf, 9, inf],

             [inf, 2, 3, inf, 0, 4, 2, inf, 8],

             [inf, inf, 6, 7, inf, 0, inf, 2, inf],

             [inf, inf, inf, inf, inf, 1, 0, inf, 3],

             [inf, inf, inf, inf, inf, inf, 1, 0, 2],

             [inf, inf, inf, inf, 8, inf, inf, 2, 0]]

m_n = len(mtx_graph)  # 带权连接矩阵的阶数

edges = []  # 保存连通的两个点之间的距离(点A、点B、距离)

for i in range(m_n):

    for j in range(m_n):

        # 去除inf和0

        if i != j and mtx_graph[i][j] != inf:

            edges.append((i, j, mtx_graph[i][j]))

# edges 就变成了带有数字的元素

def dijkstra(edges, from_node, to_node):

    global v1, path, cost

    go_path = []

    # range 从0开始 记得后面+1

    to_node = to_node - 1

    g = defaultdict(list)

    for l, r, c in edges:  # 对应dijkstra方法中的元素

        # l:点A r:点B c:距离

        # 字典： [点A -> (距离，点B)]

        g[l].append((c, r))

    q, seen = [(0, from_node - 1, ())], set()  # set集合-->去重

    while q:

        (cost, v1, path) = heappop(q)  # 堆弹出当前路径最小成本

        # seen指的是已经到达的地方

        if v1 not in seen:

            seen.add(v1)

            path = (v1, path)

            if v1 == to_node:

                break

            for c, v2 in g.get(v1, ()):

                if v2 not in seen:

                    heappush(q, (cost + c, v2, path))

    if v1 != to_node:  # 无法到达

        return float('inf'), []

    # 下面是逆序进行

    if len(path) > 0:

        left = path[0]

        go_path.append(left)

        right = path[1]

        while len(right) > 0:

            left = right[0]

            go_path.append(left)

            right = right[1]

        go_path.reverse()  # 逆序变换

        for i in range(len(go_path)):  # 标号加1

            go_path[i] = go_path[i] + 1

    return cost, go_path

leght, path = dijkstra(edges, 1, 9)

print('最短距离为：' + str(leght))

print('前进路径为：' + str(path)