I have the basic linear shortest path algorithm implemented in Python. According to various sites I've come across, this only works for directed acyclic graphs, including this, this, and this. However, I don't see why this is the case.
I've even tested the algorithm against graphs with cycles and un-directed edges, and it worked fine.
So the question is, why doesn't the linear shortest path algorithm work for non-directed cyclic graphs? Side question, what is the name of this algorithm?
For reference, here is the code I wrote for the algorithm:
def shortestPath(start, end, graph):
# First, topologically sort the graph, to determine which order to traverse it in
sorted = toplogicalSort(start, graph)
# Get ready to store the current weight of each node's path, and their predecessor
weights = [0] + [float('inf')] * (len(graph) - 1)
predecessor = [0] * len(graph)
# Next, relaxes all edges in the order of sorted nodes
for node in sorted:
for neighbour in graph[node]:
# Checks if it would be cheaper to take this path, as opposed to the last path
if weights[neighbour[0]] > weights[node] + neighbour[1]:
# If it is, then adjust the weight and predecessor
weights[neighbour[0]] = weights[node] + neighbour[1]
predecessor[neighbour[0]] = node
# Returns the shortest path to the end
path = [end]
while path[len(path) - 1] != start:
path.append(predecessor[path[len(path) - 1]])
return path[::-1]
Edit: As asked by Beta, here is the topological sort:
# Toplogically sorts the graph given, starting from the start point given.
def toplogicalSort(start, graph):
# Runs a DFS on all nodes connected to the starting node in the graph
def DFS(start):
for node in graph[start]:
if not node[0] in checked:
checked[node[0]] = True
DFS(node[0])
finish.append(start)
# Stores the finish point of all nodes in the graph, and a boolean stating if they have been checked
finish, checked = [], {}
DFS(start)
# Reverses the order of the sort, to get a proper topology; then returns
return finish[::-1]