algorithm - Floyd-Warshall: all shortest paths -


i've implemented floyd warshall return distance of shortest path between every pair of nodes/vertices , return me (but one) shortest path between each of these pairs. there anyway return every shortest path (when there multiple tied shortest) every pair of nodes? (just want know if i'm wasting time trying)

if need count of how many different shortest path exist, can keep count array in addition shortestpath array. here's quick modification of pseudocode wiki.

procedure floydwarshall () k := 1 n := 1 n j := 1 n if path[i][j] == path[i][k]+path[k][j] , k != j , k != count[i][j] += 1; else if path[i][j] > path[i][k] + path[k][j] path[i][j] = path[i][k] + path[k][j] count[i][j] = 1

if need way find paths, can store vector/arraylist structure each pair expand , collapse. here modification of pseudocode same wiki.

procedure floydwarshallwithpathreconstruction () k := 1 n := 1 n j := 1 n if path[i][k] + path[k][j] < path[i][j] path[i][j] := path[i][k]+path[k][j]; next[i][j].clear() next[i][j].push_back(k) // assuming c++ vector else if path[i][k] + path[k][j] == path[i][j] , k != j , k != next[i][j].push_back(k)

note: if k==j or k==i, means, you're checking either path[i][i]+path[i][j] or path[i][j]+path[j][j], both should equal path[i][j] , not pushed next[i][j].

path reconstruction should modified handle vector. count in case each vector's size. here modification of pseudocode (python) same wiki.

procedure getpath(i, j): allpaths = empty 2d array if next[i][j] not empty: every k in next[i][j]: if k == -1: // add path = [i, j] allpaths.add( array[ i, j] ) else: // add path = [i .. k .. j] paths_i_k = getpath(i,k) // paths k paths_k_j = getpath(k,j) // paths k j every path between , k, i_k in paths_i_k: every path between k , j, k_j in paths_k_j: i_k = i_k.popk() // remove last element since repeats in k_j allpaths.add( array( i_k + j_k) ) return allpaths

note: path[i][j] adjacency list. while initializing path[i][j], can initialize next[i][j] adding -1 array. instance initialization of next[i][j] 

for every edge (i,j) in graph: next[i][j].push_back(-1)

this takes care of edge being shortest path itself. you'll have handle special case in path reconstruction, i'm doing in getpath.


Comments

Post a Comment

Popular posts from this blog

javascript - backbone.js Collection.add() doesn't `construct` (`initialize`) an object -

<!doctype html public "-//w3c//dtd xhtml 1.0 strict//en" "http://www.w3.org/tr/xhtml1/dtd/xhtml1-strict.dtd"> <html> <head> <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script> <script src="http://documentcloud.github.com/underscore/underscore-min.js"></script> <script src="http://documentcloud.github.com/backbone/backbone-min.js"></script> </head> <body> <button id="cmd_create_event" name="cmd_create_event" type="button">create new `event`</button> <script type="text/javascript"> var eventmodel = backbone.model.extend({ initialize : function() { console.log("`event` initialized. id: " + this.cid); this.bind("change:status", function() { console.log(this.get("status") + " value `status`"); }); this.bind("error", function(model, e...
Read more

php - Get uncommon values from two or more arrays -

is there function in php give array of uncommon values 2 or more arrays? for example: $array1 = array( "green", "red", "blue"); $array2 = array( "green", "yellow", "red"); .... $result = function_needed($array1, $array2,...); print_r($result); should give output: array("blue", "yellow", ...); use array_diff , array_merge : $result = array_merge(array_diff($array1, $array2), array_diff($array2, $array1)); here's demo. for multiple arrays, combine callback , array_reduce : function unique(&$a, $b) { return $a ? array_merge(array_diff($a, $b), array_diff($b, $a)) : $b; } $arrays = array( array('green', 'red', 'blue'), array('green', 'yellow', 'red') ); $result = array_reduce($arrays, 'unique'); and here's demo of that.
Read more

Adding duplicate array rows in Php -

i create function in php adds rows of array shared column value. so input. $test = array( array("c", 5, 6), array("c", 2, 3), array("test", 5, 6) ); and output. $testduplicatefree = array( array("c", 7, 9), array("test", 5, 6) ) ); i'm thinking function combine_duplicates($array,$col){ ... ... return $duplicatefreearray; } where $col duplicate free array. so, in case, combine_duplicates($test,0); would me desired output. this. <?php function combine_duplicates($array,$col) { $index = array(); foreach ($array $row) { $key = $row[$col]; if (!isset($index[$key])) { $index[$key] = $row; } else { ($i = 0; $i < count($row); ++$i) { if ($i != $col) { $index[$key][$i] += $row[$i]; } } } } return array_values($index); } $array = array( array("c", 5, 6), array("c", 2, 3), array("test", 5, 6) ); print_r(combine_duplicates($array, 0)); try here: http://codepad.org/mdhesqhi
Read more