shortestPath.py

import math

g1 = [
    [0,    1,  2,  math.inf],
    [1,    0,  3,  4],
    [2,    3,  0,  15],
    [math.inf, 4,  15 ,0]
]

g2 = [
    [0,    1,     math.inf,  4],
    [1,    0,     2,     math.inf],
    [math.inf, 2,     0,     3],
    [4,    math.inf,  3,     0]
]

g3 = [
    [0,  2,  4,  1],
    [2,  0,  1,  3],
    [4,  1,  0,  2],
    [1,  3,  2,  0]
]

g4 = [
    [0,    1,  math.inf],
    [1,    0,  1],
    [math.inf, 1,  0]
]

def dijkstra(G, start, end=None):

    from priodict import priorityDictionary

    D = {}	# dictionary of final distances
    P = {}	# dictionary of predecessors
    Q = priorityDictionary()   # est.dist. of non-final vert.
    Q[start] = 0
	
    for v in Q:
        D[v] = Q[v]
        if v == end:
            break
        for w in G[v]:
            vwLength = D[v] + G[v][w]
            if w in D:
                if vwLength < D[w]:
                    raise (ValueError, \
                    "Dijkstra: found better path to already-final vertex")
            elif w not in Q or vwLength < Q[w]:
                Q[w] = vwLength
                P[w] = v
	
    return (D,P)
        
        
def floydWarshall(graph, begin, end):
    ''' Algoritmo de Floyd-Warshall - O(n^3)
    '''
    # Copy
    paths = list(graph)
    N = len(graph)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                paths[i][j] = min(paths[i][j], paths[i][k] + paths[k][j])
    return paths[begin][end]

# Testes e algoritmos
for alg in [floydWarshall]:
    print('=====================\n == {} ==\n====================='.format(alg.__name__))
    print('G1:')
    for i in range(3):
        for j in range(i+1, 4):
            print('From {} to {}: {}'.format(i, j, alg(g1, i, j), end=''))

    print('G2:')
    for i in range(3):
        for j in range(i+1, 4):
            print('From {} to {}: {}'.format(i, j, alg(g2, i, j), end=''))

    print('G3:')
    for i in range(3):
        for j in range(i+1, 4):
            print('From {} to {}: {}'.format(i, j, alg(g3, i, j), end=''))

    print('G4:')
    for i in range(2):
        for j in range(i+1, 3):
            print('From {} to {}: {}'.format(i, j, alg(g4, i, j), end=''))