Skip to content

Instantly share code, notes, and snippets.

@junaid1460
Last active September 26, 2017 08:43
Show Gist options
  • Save junaid1460/c6d3c96bff65d41cdb2de1751ba3c1f4 to your computer and use it in GitHub Desktop.
Save junaid1460/c6d3c96bff65d41cdb2de1751ba3c1f4 to your computer and use it in GitHub Desktop.
Floyd-warshall with Distance Vector Generator

Floyd-warshall's algorithm with Distance Vector plugin

The code below is a plugin to this algorithm to generate path.

from collections import defaultdict
import math
dist = [
[0, 1, 2, math.inf],
[math.inf, math.inf, math.inf, 1],
[math.inf, math.inf, 0, 2],
[2, math.inf, math.inf, 0],
]
path = defaultdict(defaultdict)
v = 4
for i in range(v):
for j in range(v):
for k in range(v):
val = dist[j][i] + dist[i][k]
if dist[j][k] > val:
path[j][k] = i
dist[j][k] = val
else:
try:
path[j][k]
except:
if dist[j][k] != math.inf:
path[j][k] = k
# print(dist)
# print(path)
def getPath(g, src, dst):
try:
g[src][dst]
except:
return
yield src
while src != dst:
src = g[src][dst]
yield src
pass
list(getPath(path, 1, 0))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment