Dijkstra Shortest Path Algorithm

The Dijkstra algorithm is a very popular and useful algorithm, which is used for searching the shortest path between two vertices, or between the start vertex and all other vertices at all. This algorithm isn't perfect at all, but it returns the shortest path always for a weighted graph with positive weights (or paths). Yes, sometimes edges can have a negative value of 'weight'.

This is a step-by-step algorithm to visit all the nodes, and every time update the minimum path from start to the current node. So for each vertex, we have a dist[vertex] tag – minimum path length which is found now.

Initially, the start node has tag 0 and all the other nodes have tag inf.

The algorithm is next:

Select the current vertex v . It should be the closest one (with minimum value of dist[v] ) and not visited yet.
If there is no such a vertex v or the distance to it is equal to inf , we should stop the algorithm. There is no way to access the other vertices.
For each neighbor of current node v update tags: dist[neighbor] = min(dist[neighbor], dist[v] + g[v][neighbor]) - distance has the minimum value now.
Stop if all nodes are visited.

On the gif, you can see the demo of how it works. After completing the task, the graph from a gif is created, and you can follow it step-by-step.

Tarefa

Swipe to start coding

Complete the algorithm following the comments in the code.

Solução

class Graph:

def dijkstra(self, start):

dist = [inf for v in self.g]

dist[start] = 0

visited = [False for _ in self.g]

for i in range(len(self.g)):

v = -1 # looking for the current vertex

for j in range(len(self.g)):

if not visited[j] and (v == -1 or dist[j] < dist[v]):

v = j

if dist[v] == inf:

return

visited[v] = True

for j in range(len(self.g)):

# current distance to the neighbour

l = self.g[v][j]

if l > 0:

dist[j] = min(dist[j], dist[v] + l)

print(dist)

return dist

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 3. Capítulo 2

from math import inf

class Graph:

def __init__(self, vertices=0):

# init graph with its vertices

self.g = [[0 for _ in range(vertices)] for _ in range(vertices)]

def addEdge(self, u, v, w, o = False):

# u - start vertex, v - end vertex, w - weight of edge, o - is it oriented

self.g[u][v] = w

if not o:

self.g[v][u] = w

def __str__(self):

out = ""

for row in self.g:

out += str(row) + ' '

return out

def dijkstra(self, start):

dist = [inf for v in self.g] # list of distances

# tag start vertex with 0

dist[____] = __

visited = [False for _ in self.g]

for i in range(len(self.g)):

v = -1 # looking for the current vertex

for j in range(len(self.g)):

# check if vertex j is not visited and has less tag than v

if _ _ _ _ and (v == -1 or _ _ _ < _ _ _):

# update the v

v = j

# cannot access any vertex

if dist[v] == inf:

return

visited[v] = True

for j in range(len(self.g)):

# current distance to the neighbour

l = self.g[v][j]

if l > 0: # if it is a neighbor

# update the dist[j]

dist[j] = min(_ _ _, _ _ _) # dist[j] or dist[v] + l?

print(dist)

return dist

g = Graph(6)

g.addEdge(0,1,7)

g.addEdge(0,2,9)

g.addEdge(0,5,14)

g.addEdge(1,2,10)

g.addEdge(1,3,15)

g.addEdge(2,3,11)

g.addEdge(2,5,2)

g.addEdge(4,5,9)

g.addEdge(3,4,6)

print(g)

g.dijkstra(0)

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo