python - 如何在最短路径算法中记录路径（Floyd-Warshall）

Question

我通过 Floyd-Warshall 算法找到最短路径的代码正在运行，但我需要实际存储所采用的路径，而不仅仅是最小值/成本/距离。

这是我的代码。

# import the vertices/distance matrix
import numpy as np
from datetime import datetime
import gsheets_LH

m1 = np.asarray(gsheets_LH.rangestore)

# Store destinations
firstrow = m1[0, 1:]

# Store origens
firstcolumn = m1[:, 0]

# Delete first row from table (headers)
G = np.delete(m1, 0, 0)

# Delete column, leaving only numbers/values
G = np.delete(G, 0, 1)

# The number of origins
nV = len(G)

# Defining matrix to receive result
distance = list(map(lambda i: list(map(lambda j: j, i)), G))

# Algorithm implementation for Line Haul Distance/Time Optimization


def floyd_warshall(G):
    distance = list(map(lambda i: list(map(lambda j: j, i)), G))
    # Adding vertices individually
    for k in range(nV):
        for i in range(nV):
            for j in range(nV):
                distance[i][j] = min(
                    distance[i][j], distance[i][k] + distance[k][j])

我只想存储一个矩阵或其他方式来返回给我所有节点之间的所有最短路径。

有什么帮助吗？

标签： pythonalgorithmnumpy