Floyd-warshall with Distance Vector Generator

README.md

Floyd-warshall's algorithm with Distance Vector plugin

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

floyd_warchall_with_path_generator.py

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))