Floyd-Warshall algorithm: Difference between revisions
jq
(jq) |
|||
Line 620:
console.log(graph);</lang>
=={{header|jq}}==
{{works with|jq|1.5}}
In this section, we represent the graph by a JSON object giving the weights: if u and v are the (string) labels of two nodes connected with an arrow from u to v, then .[u][v] is the associated weight:
<lang jq>
def weights: {
"1": {"3": -2},
"2": {"1" : 4, "3": 3},
"3": {"4": 2},
"4": {"2": -1}
};</lang>
The algorithm given here is a direct implementation of the definitional algorithm:
<lang jq>def fwi:
. as $weights
# construct the dist matrix
| reduce ($weights|keys[]) as $u ({};
reduce ($weights|keys[]) as $v (.;
.[$u][$v] = infinite))
| reduce ($weights|keys[]) as $u (.; .[$u][$u] = 0 )
| reduce ($weights|keys[]) as $u (.;
reduce ($weights[$u]|keys[]) as $v (.;
.[$u][$v] = $weights[$u][$v] ))
| reduce ($weights|keys[]) as $w (.;
reduce ($weights|keys[]) as $u (.;
reduce ($weights|keys[]) as $v (.;
(.[$u][$w] + .[$w][$v]) as $x
| if .[$u][$v] > $x then .[$u][$v] = $x
else . end ))) ;
weights | fwi</lang>
{{out}}
<pre>{
"1": {
"1": 0,
"2": -1,
"3": -2,
"4": 0
},
"2": {
"1": 4,
"2": 0,
"3": 2,
"4": 4
},
"3": {
"1": 5,
"2": 1,
"3": 0,
"4": 2
},
"4": {
"1": 3,
"2": -1,
"3": 1,
"4": 0
}
}</pre>
=={{header|Kotlin}}==
| |||