I have this python file in which I implemented dijkstra's algorithm iteratively. Graphs are given in adjacency matrix format.
The thing is that in the last case of the test block this is the expected result: [13.0, 10.0, 14.0, 0.0, 6.0, 7.0, 8.0] and this is the result I'm getting: [13.0, 10.0, 18.0, 0.0, 6.0, 7.0, 8.0]
I don't have any errors in the rest of the cases, that's the only weird case I get.
Any ideas on why is this?
Here's the code:
from time import time
from math import inf
import math
# function to get the node with the minimum distance in shortest_path_list
# that hasn't been visited
def min_dist_node(graph, visited, sp_list, current_node):
dist = inf
node = 0
for i in range(0, len(graph)):
if i != current_node and not math.isinf(graph[current_node][i]) and dist > graph[current_node][i] and not visited[i]:
dist = graph[current_node][i]
node = i
return node
# Dijkstra's algorithm
def Dijkstra (graph, initial):
sp_list = []
visited = [False]*len(graph)
for node in range(0, len(graph)):
sp_list.append(graph[initial][node])
sp_list[initial] = 0.0
visited[initial] = True
current_node = initial
while False in visited:
current_node = min_dist_node(graph, visited, sp_list, current_node)
visited[current_node] = True
for node in range(0, len(graph)):
if sp_list[node] > sp_list[current_node] + graph[current_node][node]:
sp_list[node] = sp_list[current_node] + graph[current_node][node]
return sp_list
def test():
g0 = [[0.0, 5.0, 1.0, inf],
[5.0, 0.0, 1.0, 2.0],
[1.0, 1.0, 0.0, 10.0],
[inf, 2.0, 10.0, 0.0]]
assert Dijkstra(g0, 3) == [4.0, 2.0, 3.0, 0.0]
g1 = [[0.0, 2.0],
[2.0, 0.0]]
assert Dijkstra(g1,0) == [0.0,2.0]
g2 = [[0.0, 5.0, 3.0],
[5.0, 0.0, inf],
[3.0, inf, 0.0]]
assert Dijkstra(g2, 1) == [5.0, 0.0, 8.0]
g3 = [[0.0, 1.0, 2.0, 3.0, 4.0],
[1.0, 0.0, inf, inf, 8.0],
[2.0, inf, 0.0, 2.0, 2.0],
[3.0, inf, 2.0, 0.0, 5.0],
[4.0, 8.0, 2.0, 5.0, 0.0]]
assert Dijkstra(g3, 3) == [3.0, 4.0, 2.0, 0.0, 4.0]
g4 = [[0.0, 6.0, 2.0, 5.0],
[6.0, 0.0, 4.0, inf],
[2.0, 4.0, 0.0, 2.0],
[5.0, inf, 2.0, 0.0]]
assert Dijkstra(g4, 3) == [4.0, 6.0, 2.0, 0.0]
g5 = [[0.0, 10.0, 1.0, inf, inf, inf],
[10.0, 0.0, inf, 5.0, 4.0, inf],
[1.0, inf, 0.0, 8.0, 2.0, 3.0],
[inf, 5.0, 8.0, 0.0, inf, 2.0],
[inf, 4.0, 2.0, inf, 0.0, inf],
[inf, inf, 3.0, 2.0, inf, 0.0]]
assert Dijkstra(g5, 0) == [0.0, 7.0, 1.0, 6.0, 3.0, 4.0]
g6 = [[0.0, 3.0, 1.0, inf, inf, inf, inf],
[3.0, 0.0, 8.0, 10.0, 5.0, inf, inf],
[1.0, 8.0, 0.0, inf, inf, inf, inf],
[inf, 10.0, inf, 0.0, 6.0, inf, 9.0],
[inf, 5.0, inf, 6.0, 0.0, 1.0, 2.0],
[inf, inf, inf, inf, 1.0, 0.0, 4.0],
[inf,inf,inf, 9.0, 2.0, 4.0, 0.0]]
print(Dijkstra(g6, 3))
assert Dijkstra(g6, 3) == [13.0, 10.0, 14.0, 0.0, 6.0, 7.0, 8.0]
start_time = time()
test()
elapsed_time = time() - start_time
print("Elapsed time: %0.10f seconds." % elapsed_time)
Update! I found a way of solving without using priority queues. In the min_dist_node function if we put dist >= graph[initial][i] we'll consider first all distances (from the initial node) non equal to inf and then all the inf ones.
I think this is the right way, if anyone does see some mistake let me know!
This is how all the algorith looks like now:
from time import time
from math import inf
# function to get the node with the minimum distance in shortest_path_list
# that hasn't been visited
def min_dist_node(graph, visited, sp_list, initial):
dist = inf
node = 0
for i in range(0, len(graph)):
if i != initial and dist >= graph[initial][i] and not visited[i]:
dist = graph[initial][i]
node = i
return node
# Dijkstra's algorithm
def Dijkstra (graph, initial):
sp_list = []
visited = [False]*len(graph)
for node in range(0, len(graph)):
sp_list.append(graph[initial][node])
visited[initial] = True
while False in visited:
current_node = min_dist_node(graph, visited, sp_list, initial)
visited[current_node] = True
for node in range(0, len(graph)):
if sp_list[node] > sp_list[current_node] + graph[current_node][node]:
sp_list[node] = sp_list[current_node] + graph[current_node][node]
return sp_list
def test():
g0 = [[0.0, 5.0, 1.0, inf],
[5.0, 0.0, 1.0, 2.0],
[1.0, 1.0, 0.0, 10.0],
[inf, 2.0, 10.0, 0.0]]
assert Dijkstra(g0, 3) == [4.0, 2.0, 3.0, 0.0]
g1 = [[0.0, 2.0],
[2.0, 0.0]]
assert Dijkstra(g1,0) == [0.0,2.0]
g2 = [[0.0, 5.0, 3.0],
[5.0, 0.0, inf],
[3.0, inf, 0.0]]
assert Dijkstra(g2, 1) == [5.0, 0.0, 8.0]
g3 = [[0.0, 1.0, 2.0, 3.0, 4.0],
[1.0, 0.0, inf, inf, 8.0],
[2.0, inf, 0.0, 2.0, 2.0],
[3.0, inf, 2.0, 0.0, 5.0],
[4.0, 8.0, 2.0, 5.0, 0.0]]
assert Dijkstra(g3, 3) == [3.0, 4.0, 2.0, 0.0, 4.0]
g4 = [[0.0, 6.0, 2.0, 5.0],
[6.0, 0.0, 4.0, inf],
[2.0, 4.0, 0.0, 2.0],
[5.0, inf, 2.0, 0.0]]
assert Dijkstra(g4, 3) == [4.0, 6.0, 2.0, 0.0]
g5 = [[0.0, 10.0, 1.0, inf, inf, inf],
[10.0, 0.0, inf, 5.0, 4.0, inf],
[1.0, inf, 0.0, 8.0, 2.0, 3.0],
[inf, 5.0, 8.0, 0.0, inf, 2.0],
[inf, 4.0, 2.0, inf, 0.0, inf],
[inf, inf, 3.0, 2.0, inf, 0.0]]
assert Dijkstra(g5, 0) == [0.0, 7.0, 1.0, 6.0, 3.0, 4.0]
g6 = [[0.0, 3.0, 1.0, inf, inf, inf, inf],
[3.0, 0.0, 8.0, 10.0, 5.0, inf, inf],
[1.0, 8.0, 0.0, inf, inf, inf, inf],
[inf, 10.0, inf, 0.0, 6.0, inf, 9.0],
[inf, 5.0, inf, 6.0, 0.0, 1.0, 2.0],
[inf, inf, inf, inf, 1.0, 0.0, 4.0],
[inf,inf,inf, 9.0, 2.0, 4.0, 0.0]]
print(Dijkstra(g6, 3))
assert Dijkstra(g6, 3) == [13.0, 10.0, 14.0, 0.0, 6.0, 7.0, 8.0]
start_time = time()
test()
elapsed_time = time() - start_time
print("Elapsed time: %0.10f seconds." % elapsed_time)