Plus court chemin

In [14]:
def dimensions(M):
    return len(M), len(M[0])

def matrice_nulle(n, p):
    # ne pas écrire [[0]*p]*n
    return [[0]*p for i in range(n)]

matrice_nulle(2, 3)
Out[14]:
[[0, 0, 0], [0, 0, 0]]
In [15]:
def copie_matrice(M):
    lig, col = dimensions(M)
    copie = matrice_nulle(lig, col)
    for i in range(lig):
        for j in range(col):
            copie[i][j] = M[i][j]
    return copie

Floyd-Warshall

$D^{(k+1)}_{i, j} = min(D^{(k)}_{i, j}, D^{(k)}_{i, k}+D^{(k)}_{k, j})$

In [13]:
inf = float('inf')             # Python/Ocaml

graphe_matrice = [
    [0  ,   3,   8, inf,   4],
    [inf,   0, inf,   1,   7],
    [inf,   4,   0, inf, inf],
    [2  , inf,   5,   0, inf],
    [inf, inf, inf,   6,   0],
]
In [58]:
def floyd_warshall_bis(graphe):
    n = len(graphe)
    D  = copie_matrice(graphe)
    D1 = matrice_nulle(n, n)
    for k in range(0, n):        # bornes
        for i in range(n):
            for j in range(n):
                D1[i][j] = min(D[i][j], D[i][k]+D[k][j])
        D = copie_matrice(D1)
    return D1

floyd_warshall(graphe_matrice)
Out[58]:
[[0, 3, 8, 4, 4],
 [3, 0, 6, 1, 7],
 [7, 4, 0, 5, 11],
 [2, 5, 5, 0, 6],
 [8, 11, 11, 6, 0]]
In [56]:
def floyd_warshall(graphe):
    D = copie_matrice(graphe)
    n = len(graphe)
    for k in range(0, n):      # bornes
        for i in range(n):
            for j in range(n):
                D[i][j] = min(D[i][j], D[i][k]+D[k][j])

    return D

floyd_warshall(graphe_matrice)
Out[56]:
[[0, 3, 8, 4, 4],
 [3, 0, 6, 1, 7],
 [7, 4, 0, 5, 11],
 [2, 5, 5, 0, 6],
 [8, 11, 11, 6, 0]]

Dijkstra

In [41]:
graphe_liste = [[(1, 3), (2, 8), (4, 4)], [(3, 1), (4, 7)], [(1, 4)], [(0, 2), (2, 5)], [(3, 6)]]
In [52]:
from heapq import heappush, heappop   # heapq
# File de priorité : (dist, sommet)

inf = float('inf')

def dijkstra(voisins, source):        # pere ; vu ; _
    fileprio, d = [], [inf]*len(graphe)
    d[source] = 0
    heappush(fileprio, (0, source))
    while fileprio != []:
        _, u = heappop(fileprio)
        for v, dist in voisins[u]:
            nouvelle = d[u]+dist
            if  nouvelle < d[v]:
                d[v] = nouvelle
                heappush(fileprio, (nouvelle, v))
    return d
In [53]:
[dijkstra(graphe_liste, s) for s in range(len(graphe_liste))]
Out[53]:
[[0, 3, 8, 4, 4],
 [3, 0, 6, 1, 7],
 [7, 4, 0, 5, 11],
 [2, 5, 5, 0, 6],
 [8, 11, 11, 6, 0]]
In [ ]:
In [ ]:
In [ ]: