L'algorithme de Dijkstra en Python

L’algorithme de Dijkstra peut être défini comme un algorithme glouton qui peut être utilisé pour trouver la distance la plus courte possible d’un sommet source à tout autre sommet possible existant dans un graphe pondéré, à condition que le sommet soit accessible depuis le sommet source.

Ce tutoriel explique comment implémenter l’algorithme de Dijkstra pour trouver le chemin le plus court en Python.

Comme mentionné ci-dessus, l’algorithme de Dijkstra est gourmand. Un algorithme glouton peut être défini comme un paradigme algorithmique qui se concentre sur la construction d’une solution pièce par pièce au problème donné, en choisissant ensuite l’option la plus avantageuse.

Le fonctionnement de l’algorithme de Dijkstra est le suivant.

• Étant donné quelques sommets non visités, sélectionnez le sommet avec la plus petite distance de la source et visitez-le.
• La distance pour chaque voisin est alors mise à jour. La même chose est faite pour le sommet visité, qui a une distance actuelle supérieure à la somme et au poids de l’arête donnée entre eux.
• Les étapes 1 et 2 doivent être répétées jusqu’à ce qu’il n’y ait plus de sommets non visités.

L’algorithme de Dijkstra ressemble à l’algorithme Minimum Spanning Tree de Prim, un autre algorithme Greedy, car les deux nécessitent la génération d’un SPT (arbre du chemin le plus court), prenant la source comme racine de l’arbre.

Le code suivant utilise l’algorithme de Dijkstra pour trouver le chemin le plus court en Python.

import sys


class Graph:
    def __init__(self, vertx):
        self.V = vertx
        self.graph = [[0 for column in range(vertx)] for row in range(vertx)]

    def pSol(self, dist):
        print("Distance of vertex from source")
        for node in range(self.V):
            print(node, "t", dist[node])

    def minDistance(self, dist, sptSet):

        min = sys.maxsize

        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    def dijk(self, source):

        dist = [sys.maxsize] * self.V
        dist[source] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            u = self.minDistance(dist, sptSet)

            sptSet[u] = True

            for v in range(self.V):
                if (
                    self.graph[u][v] > 0
                    and sptSet[v] == False
                    and dist[v] > dist[u] + self.graph[u][v]
                ):
                    dist[v] = dist[u] + self.graph[u][v]

        self.pSol(dist)


f = Graph(9)
f.graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0],
]

f.dijk(0)

Le code ci-dessus fournit la sortie suivante :

Distance of vertex from source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14

L’algorithme de Dijkstra est très similaire à l’algorithme Depth First Search, bien que ces deux algorithmes n’existent pas précisément dans le même but.

La seule différence significative entre Depth First Search et l’algorithme de Dijkstra est que le premier fonctionne plus lentement que le second car l’algorithme Depth First Search (DFS) utilise la technique de la pile. D’autre part, l’algorithme de Dijkstra utilise la technique du tas comparativement plus lente.