K Shortest Path Python Not Working

I'm having certain Issues with my K Shortest Path algorithm. The code is given as: def K_shortest_Paths(graph,S,T,K=4): '''Initialize Variables Accordingly''' B = {} P

Solution 1:

If you call K_shortest_Pathes(graph, "11", "10") you will never add an element to the set P. Read my inline comments.

def K_shortest_Paths(graph,S,T,K=4):
    '''Initialize Variables Accordingly'''
    B = {}
    P = set()
    count = {}
    for U in graph.keys():
        count[U] = 0

    # currently the B has only one item, i.e. { S: 0 } => { "11": 0 }
    B[S] = 0

    '''Algorithm Starts'''
    while(len(B)>=1 and count[T]<K):

        # results in the only key in B, i.e. PU = S => PU = "11"
        PU = min(B,key=lambda x:B[x])

        cost = B[PU]

        # U = PU[len(PU) - 1], where PU = "11" => 
        # U = "11"[len("11")-1] => 
        # *** U = "1"
        U = PU[len(PU)-1]

        del B[PU]
        count[U] += 1

        # *** U == T => "1" == T => "1" == "10" which is False
        # Thus nothing is ever added to set P  
        if U==T:
            P.add(PU)

        if count[U]<=K:
            V = graph[U].keys()
            for v in V:
                if v not in PU:
                    PV = PU+v
                    B[PV] = cost+1        
    return P

Solution 2:

What I presume you are trying to achieve. Try this.

def k_shortest_paths(graph, src_node, dest_node, k=4):
  result = []
  pathes = [[src_node]]
  while len(pathes) > 0 and len(result) < k:
    path = pathes.pop()
    last_node = path[-1]
    if last_node == dest_node:
      result.append(path)
    else:
      for child_node in graph[last_node].keys():
        if child_node not in path:
          pathes.append(path + [child_node])
  return result