Search code examples
algorithmgraphnetworkxpython-3.7

Yen's K shortest Path giving incorrect results (Python)

I am trying to implement the Yen's K Shortest Path Algorihtm based on the pseudo-code from https://en.wikipedia.org/wiki/Yen%27s_algorithm. Here is the code. 

import numpy as np
import networkx as nx

edge_list = [[0, 1], [0, 2], [0, 7], [1, 2], [1, 9], [2, 5], [2, 7], [2, 9], [3, 4], [3, 5], [3, 6], [3, 8], [4, 5], [4, 6], [4, 7], [4, 8], [5, 6], [5, 7], [5, 8], [6, 8], [7, 8]]
graph = nx.Graph()
graph.add_edges_from(edge_list)
nx.draw(graph, with_labels = True)
source_node = 8
destination_node = 9

def yen_ksp(graph, source, sink, K):
    A, B = [], []
    A.append(nx.shortest_path(graph, source=source, target=sink))
    for k in range(1, 1+K):
        for i in range(len(A[k - 1]) - 1):
            spurNode = A[k-1][i]
            rootPath = A[k-1][0:i+1]
            removed_edges, removed_nodes = [], []
            for p in A:
                if rootPath == p[0:i+1] and p[i:i+2] not in removed_edges:
                    removed_edges.append(p[i:i+2])

            for edge in removed_edges:
                graph.remove_edge(edge[0], edge[1])
            try:
                spurPath = nx.shortest_path(graph, source=spurNode, target=sink)
            except:
                for edge in removed_edges:
                    graph.add_edge(edge[0], edge[1])
                continue

            totalPath = rootPath + spurPath[1:]
            B.append(totalPath)
            for edge in removed_edges:
                graph.add_edge(edge[0], edge[1])

        if B == []:
# This handles the case of there being no spur paths, or no spur paths left.
# This could happen if the spur paths have already been exhausted (added to A), 
# or there are no spur paths at all - such as when both the source and sink vertices 
# lie along a "dead end".
           break
        B.sort()
        A.append(B[-1])
        B.pop(-1)
    return A

print(yen_ksp(graph.copy(), source_node, destination_node, 10))

This is supposed to be an undirected, unweighted graph generated from the above code.

undirected, unweighted graph

And this is the output of the code.

[[8, 5, 2, 9],
 [8, 7, 2, 9],
 [8, 7, 2, 1, 9],
 [8, 7, 2, 1, 2, 9],
 [8, 7, 2, 1, 2, 1, 9],
 [8, 7, 2, 1, 2, 1, 2, 9],
 [8, 7, 2, 1, 2, 1, 2, 1, 9],
 [8, 7, 2, 1, 2, 1, 2, 1, 2, 9],
 [8, 7, 2, 1, 2, 1, 2, 1, 2, 1, 9],
 [8, 7, 2, 1, 2, 1, 2, 1, 2, 1, 2, 9],
 [8, 7, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 9]]

Obviously there are shorter paths that the algorithm missed. And, the results contain paths that have loops. I want only the ones without.

Also, in other cases, the results were in the wrong order, some longer paths appear before other paths that are shorter. In the KSP problem, the order of results is obviously important because if I stop at some k, I want to be sure that there is no shorter path that I have missed.

I am open to other algorithms that can correctly and effectively solve this problem of KSP without loops on undirected-unweighted graphs.

Please help.

Solution

  • Networkx provides a function for generating a list of all simple paths in a graph from source to target, starting from shortest ones: shortest_simple_paths. This procedure is based exactly on Yen's algorithm, as you can read in the documentation.

    Using it is very simple:

    paths = list(nx.shortest_simple_paths(graph, source_node, target_node))

    If you want only the first K shortest paths you can make use of islice:

    from itertools import islice
paths = list(islice(nx.shortest_simple_paths(graph, source_node, target_node), K))

    Example:

    from itertools import islice

K = 10
source_node = 8
target_node = 9

graph = nx.Graph()
edge_list = [[0, 1], [0, 2], [0, 7], [1, 2], [1, 9], [2, 5], [2, 7],
             [2, 9], [3, 4], [3, 5], [3, 6], [3, 8], [4, 5], [4, 6],
             [4, 7], [4, 8], [5, 6], [5, 7], [5, 8], [6, 8], [7, 8]]
graph.add_edges_from(edge_list)

for path in islice(nx.shortest_simple_paths(graph, source_node, target_node), K):
    print(path)

    Output:

    [8, 5, 2, 9]
[8, 7, 2, 9]
[8, 5, 7, 2, 9]
[8, 5, 2, 1, 9]
[8, 3, 5, 2, 9]
[8, 7, 0, 1, 9]
[8, 7, 2, 1, 9]
[8, 4, 5, 2, 9]
[8, 7, 5, 2, 9]
[8, 7, 0, 2, 9]

    If you want to understand how shortest_simple_path is implemented you can check out its source code: it's well written and very easy to understand!