使用Floyd-Warshall算法进行路径重建。

我正在尝试从我在Lua中实现的Floyd-Warshall算法中重构两个顶点之间的最小成本路径。

这是我到目前为止写的内容：

function shallow_copy(g)
    local h = {}
    for k, v in pairs(g) do
        h[k] = v
    end
    return h
end

function fw(g) -- g is an adjacency matrix representing the graph
    local d = shaloow_copy(g)
    for k = 1, #d do
        for i = 1, #d do
            for j = 1, #d do
                d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])
            end
        end
    end
    return d
end

这些函数给我一个矩阵，其中包含我图形中每对顶点之间分离长度（边数），这非常方便。

现在，我需要知道任何给定顶点之间的实际路径。维基百科提供了伪代码，但–作为新手–我不知道如何实现它。

这是维基百科文章中提供的伪代码（https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm#Path_reconstruction）：

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction ()
   for each vertex v
      dist[v][v] ← 0
   for each edge (u,v)
      dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
   for k from 1 to |V|
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]
               next[i][j] ← k

function Path (i, j)
   if dist[i][j] = ∞ then
     return "no path"
   var intermediate ← next[i][j]
   if intermediate = null then
     return " "   // the direct edge from i to j gives the shortest path
   else
     return Path(i, intermediate) + intermediate + Path(intermediate, j)

有人知道如何在lua中实现这个伪代码吗？我需要重新编写我的短lua代码还是可以将此伪代码某些方式合并到我已经拥有的代码中？

干杯！