Algoritmo de Dijkstra em Python

O algoritmo de Dijkstra pode ser definido como um algoritmo guloso que pode ser utilizado para descobrir a menor distância possível de um vértice de origem a qualquer outro vértice possível que exista em um gráfico ponderado, desde que o vértice seja alcançável a partir do vértice de origem.

Este tutorial discute como implementar o algoritmo de Dijkstra para encontrar o caminho mais curto em Python.

Como mencionado acima, o algoritmo de Dijkstra é ganancioso. Um algoritmo ganancioso pode ser definido como um paradigma algorítmico que se concentra na construção de uma solução peça por peça para um determinado problema, escolhendo então a opção mais benéfica.

O algoritmo de Dijkstra funciona da seguinte maneira.

• Dados alguns vértices não visitados, selecione o vértice com a menor distância da fonte e visite-o.
• A distância para cada vizinho é então atualizada. O mesmo é feito para o vértice visitado, que possui uma distância atual maior que a soma e o peso da aresta dada entre eles.
• Os passos 1 e 2 precisam ser repetidos até que não haja vértices não visitados.

O algoritmo de Dijkstra tem uma semelhança com o algoritmo Minimum Spanning Tree de Prim, outro algoritmo Greedy, pois ambos precisam da geração de um SPT (shortest path tree), tomando a fonte como a raiz da árvore.

O código a seguir usa o algoritmo de Dijkstra para encontrar o caminho mais curto em 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)

O código acima fornece a seguinte Resultado:

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

O algoritmo de Dijkstra é muito semelhante ao algoritmo Depth First Search, embora ambos os algoritmos não existam precisamente para o mesmo propósito.

A única diferença significativa entre a primeira pesquisa de profundidade e o algoritmo de Dijkstra é que o primeiro funciona mais devagar do que o último, pois o algoritmo de primeira pesquisa de profundidade (DFS) usa a técnica de pilha. Por outro lado, o algoritmo de Dijkstra faz uso da técnica de heap comparativamente mais lenta.