dijkstra-python/Dijkstra2.py at master · RafaSRibeiro/dijkstra-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from collections import defaultdict
from math import inf


class Grafo:
  def __init__(self):
    self.vertices = set()
    self.arestas = defaultdict(list)
    self.distancias = {}

  def addVertice(self, value):
    self.vertices.add(value)

  def addAresta(self, verticeOrigem, verticeDestino, distancia):
    self.arestas[verticeOrigem].append(verticeDestino)
    self.distancias[(verticeOrigem, verticeDestino)] = distancia


distancia = {}
caminho = {}


def Dijkstra(grafo, verticeOrigem):
  for vertice in grafo.vertices:
    distancia[vertice] = inf
    caminho[vertice] = None
  distancia[verticeOrigem] = 0;

  vertices = set(grafo.vertices)
  while len(vertices) > 0:
    verticeMenorDistancia = menorDistancia(vertices)
    vertices.remove(verticeMenorDistancia)
    for vizinho in grafo.arestas[verticeMenorDistancia]:
      alt = distancia[verticeMenorDistancia] + grafo.distancias[(verticeMenorDistancia, vizinho)]
      if alt < distancia[vizinho]:
        distancia[vizinho] = alt
        caminho[vizinho] = verticeMenorDistancia

  print(caminho)
  menorCaminho = list()
  verticeAnterior = None
  for vertice in caminho:
    # print(vertice)
    # print(caminho[vertice])
    # print(distancia[vertice])
    if caminho[vertice] == verticeAnterior:
      menorCaminho.append(vertice)


  print(menorCaminho)


def menorDistancia(vertices):
  menorDistancia = inf
  verticeMenorDistancia = None
  for vertice in vertices:
    if distancia[vertice] < menorDistancia:
      menorDistancia = distancia[vertice]
      verticeMenorDistancia = vertice

  return verticeMenorDistancia


grafo = Grafo()

grafo.addVertice(1)
grafo.addVertice(2)
grafo.addVertice(3)
grafo.addVertice(4)
grafo.addVertice(5)
grafo.addVertice(6)

grafo.addAresta(1, 2, 7)
grafo.addAresta(1, 3, 3)
grafo.addAresta(2, 3, 1)
grafo.addAresta(2, 4, 6)
grafo.addAresta(4, 4, 4)
grafo.addAresta(3, 5, 8)
grafo.addAresta(5, 4, 2)
grafo.addAresta(5, 6, 8)
grafo.addAresta(4, 6, 2)

Dijkstra(grafo, 1)