Python Algorithm Pt.9: Dijkstra

I bet ya’ 49$ you can not say its name first try. DIJKSTRA. Try again. DIJKSTRA. Still can not get it right? Do I care? Hmm. No. Do you care? Do I care if you care? Hmm. No. Let’s get right into it. Also, don’t forget my 49$.

Dijkstra is a algorithm used to find the shortest route from one point to another. The distance between different points are combined and calculated to form a matrix of different points connected to each other, with the distance between them written on the line between, and using the algorithm to search every possible sum of the distance combined and at the same time checking each of them and comparing them. The smallest sum of the distance is the nearest, hence completing the algorithm’s task and, depending on the user’s wish, outputting it in the terminal.

A method to understand dijkstra is by drawing a table. In the table we have the shortest distance from a point, the vertex, and the previous vertex. Using this table we can see how the code functions and how it goes through every possibility: By calculating each line and distance, adding them up, and comparing.

Here is an example:

def dijkstra(graph, start):
visited = []
index = start
nodes = dict((i, INF) for i in graph)
nodes[start] = 0
while len(visited) < len(graph):
visited.append(index)
for i in graph[index]:
new_cost = nodes[index] + graph[index][i]
if new_cost < nodes[i]:
nodes[i] = new_cost
next = INF
for n in nodes:
continue
if nodes[n] < next:
next = nodes[n]
index = n
return nodes
INF = 9999
graph = {'A':{'A':0, 'B':2, 'C':4},
'B':{'B':0, 'C':7, 'E':6},
'C':{'C':0, 'D':6, 'E':2},
'D':{'D':0, 'E':8, 'G':4},
'E':{'E':0, 'G':2},
'G':{'G':0}
}
rtn = dijkstra(graph, 'A')
print(rtn)

Here is the output of the example above:

Result

derp.