Code : Algorithme de Dijkstra

Génération de graphe aléatoire¶

In [1]:

try:
    __import__("cpge")
except ImportError:
    ! pip install git+https://github.com/fortierq/itc-code &> /dev/null
import cpge.graph

G = cpge.graph.random_matrix(directed=True, weighted=True)
cpge.graph.draw(G, directed=True, weighted=True)
G

try: __import__("cpge") except ImportError: ! pip install git+https://github.com/fortierq/itc-code &> /dev/null import cpge.graph G = cpge.graph.random_matrix(directed=True, weighted=True) cpge.graph.draw(G, directed=True, weighted=True) G

Out[1]:

[[inf, inf, inf, inf, 4, inf, 7, inf],
 [7, inf, 7, 2, 6, inf, inf, 8],
 [inf, inf, inf, inf, inf, inf, inf, inf],
 [inf, 1, inf, inf, 2, 1, inf, inf],
 [inf, inf, inf, inf, inf, 7, inf, inf],
 [8, 6, inf, 3, inf, inf, inf, inf],
 [inf, 8, 1, 5, 6, 3, inf, 3],
 [inf, 3, inf, 9, inf, 6, 5, inf]]

Calcul des distances¶

In [2]:

from cpge import PriorityQueue

def dijkstra(G, s):
    n = len(G)
    dist = n*[float("inf")]
    dist[s] = 0
    q = PriorityQueue()
    for v in range(n):
        q.add(v, dist[v])

    while not q.is_empty():
        u = q.take_min()
        for v in range(n):
            d = dist[u] + G[u][v]
            if v in q and d < dist[v]:
                q.update(v, d)
                dist[v] = d
    return dist


dijkstra(G, 0)

from cpge import PriorityQueue def dijkstra(G, s): n = len(G) dist = n*[float("inf")] dist[s] = 0 q = PriorityQueue() for v in range(n): q.add(v, dist[v]) while not q.is_empty(): u = q.take_min() for v in range(n): d = dist[u] + G[u][v] if v in q and d < dist[v]: q.update(v, d) dist[v] = d return dist dijkstra(G, 0)

Out[2]:

[0, 13, 8, 12, 4, 10, 7, 10]

Animation¶

In [3]:

cpge.graph.anim_dijkstra(G, 0)

cpge.graph.anim_dijkstra(G, 0)

Out[3]:

Once Loop Reflect