lua - Floyd-Warshall path reconstruction -


i'm trying reconstruct least cost path between 2 vertices floyd-warshall algorithm implemented in lua.

here i've written far:

function shallow_copy(g)     local h = {}     k, v in pairs(g)         h[k] = v     end     return h end  function fw(g) -- g adjacency matrix representing graph     local d = shaloow_copy(g)     k = 1, #d         = 1, #d             j = 1, #d                 d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])             end         end     end     return d end 

these functions give me matrix containing length (number of edges) separating each pair of vertices in graph g, great.

i need know actual path between given vertices. wikipedia conveniently provides pseudo code, -being newbie- i'm confuse how implement it.

here pseudocode provided in wikipedia article (https://en.wikipedia.org/wiki/floyd–warshall_algorithm#path_reconstruction):

let dist |v| × |v| array of minimum distances initialized ∞ (infinity) let next |v| × |v| array of vertex indices initialized null  procedure floydwarshallwithpathreconstruction ()    each vertex v       dist[v][v] ← 0    each edge (u,v)       dist[u][v] ← w(u,v)  // weight of edge (u,v)    k 1 |v|       1 |v|          j 1 |v|             if dist[i][k] + dist[k][j] < dist[i][j]                dist[i][j] ← dist[i][k] + dist[k][j]                next[i][j] ← k  function path (i, j)    if dist[i][j] = ∞      return "no path"    var intermediate ← next[i][j]    if intermediate = null      return " "   // direct edge j gives shortest path    else      return path(i, intermediate) + intermediate + path(intermediate, j) 

would know how implement pseudo code in lua? need re-write short piece of lua code or can pseudocode somehow merged i've got?

cheers!


Comments

Popular posts from this blog

php - regexp cyrillic filename not matches -

c# - OpenXML hanging while writing elements -

sql - Select Query has unexpected multiple records (MS Access) -