Question

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]
Was it helpful?

Solution

Because you cannot topologically sort a graph with cycles (therefore undirected graphs are also out of the question as you can't tell which node should come before another).

Edit: After reading the comments, I think that's actually what @Beta meant.

OTHER TIPS

When there is cycle, topological sort cannot guarantee the correct ordering of the shortest path.

For example, we have a graph:

A->C, A->B, B->C, C->B, B->D

Say the correct shortest path is:

A->C->B->D

But topological sort can generate an order:

A->B->C->D

Although it will update B to the correct order when visiting C, but B won't be visited again, thus not able to propagate correct weight to D. (Path happens to be correct though.)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top