1

我正在尝试从我在 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

这些函数为我提供了一个矩阵，其中包含分隔图 g 中每对顶点的长度（边数），这很棒。

我现在需要知道任何给定顶点之间的实际路径。维基百科方便地提供了伪代码，但是——作为一个新手——我对如何实现它感到困惑。

这是维基百科文章中提供的伪代码（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 代码，或者这个伪代码可以以某种方式合并到我所拥有的中？

干杯!

4

0 回答 0