1

Lua で実装した Floyd-Warshall アルゴリズムから 2 つの頂点間の最小コスト パスを再構築しようとしています。

ここに私がこれまでに書いたものがあります：

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