77509

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 = set() count = {} for U in graph.keys(): count[U] = 0 B[S] = 0 '''Algorithm Starts''' while(len(B)>=1 and count[T]<K): PU = min(B,key=lambda x:B[x]) cost = B[PU] U = PU[len(PU)-1] del B[PU] count[U] += 1 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

This is equivalent to https://en.wikipedia.org/wiki/K_shortest_path_routing which provides the Pseudo Code for Implementation. The Graph is given as: Now, It works well if I have Starting Node S<10, and Terminating Node T<10, but with S and T>10, it returns an empty set, Whereas it should return the Path. Please Note that I can't Use Networkx libraries. I only have to Use basic libraries in Python

Furthermore, the Code to Generate Graph is this:

def create_dictionary(graph): D = {} for item in graph.items(): temp = {} connected = list(item[1]) key = item[0] for V in connected: temp[str(V)] = 1 D[str(key)] = temp return D def gen_p_graph(nodes,prob): if prob>1: er='error' return er graph_matrix=np.zeros([nodes,nodes]) num_of_connections=int(((nodes * (nodes-1)) * prob )/2) num_list_row=list(range(nodes-1)) while(np.sum(np.triu(graph_matrix))!=num_of_connections): row_num=random.choice(num_list_row) num_list_col=(list(range(row_num+1,nodes))) col_num=random.choice(num_list_col) if graph_matrix[row_num,col_num]==0: graph_matrix[row_num,col_num]=1 graph_matrix[col_num,row_num]=1 #create dictionary df=pd.DataFrame(np.argwhere(graph_matrix==1)) arr=np.unique(df.iloc[:,0]) dct={} for i in range(graph_matrix.shape[0]): dct[str(i)]=set() for val in arr: dct[str(val)].update(df.loc[df.iloc[:,0]==val].iloc[:,1].values) return pd.DataFrame(graph_matrix),dct

And I run it like this:

graph= create_dictionary(gen_p_graph(100,0.8)[1]) K_shortest_Paths(graph,'11','10')

return an empty set whereas it should return paths.

Answer1:

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

Answer2:

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

Recommend

  • how do you “Press ENTER to continue, anything else to quit” in C++
  • Can't add target for UIButton - unrecognised selector sent to instance, despite method been in
  • What to use (best/good practice) for the secret key in HMAC solution?
  • C++, user input check for '\\0' stops at spaces?
  • Facebook Friend Request - Error - 'All users in param ids must have accepted TOS'
  • Rely on Facebook user id as a permanent user identifier
  • What does the “?” mean in the following statement
  • How do you compute the XOR Remainder used in CRC?
  • eC (Ecere) how to not worry about private data fields of a class
  • unrecognized selector isPitched called
  • c++ search a vector for element first seen position
  • How to add learning rate to summaries?
  • Is there any purpose for h2-h6 headings in HTML5?
  • Double dispatch in Java example
  • abstracting over a collection
  • How can I include If-None-Match header in HttpRequestMessage
  • Simple linked list-C
  • Can't remove headers after they are sent
  • C++ pointer value changes with static_cast
  • CakePHP ACL tutorial initDB function warnings
  • WPF ICommand CanExecute(): RaiseCanExecuteChanged() or automatic handling via DispatchTimer?
  • Parse a date string in a specific locale (not timezone!)
  • iOS: Detect app start via notification press
  • ImageMagick, replace semi-transparent white with opaque white
  • formatting the colorbar ticklabels with SymLogNorm normalization in matplotlib
  • Cannot connect to cassandra from Spark
  • Display issues when we change from one jquery mobile page to another in firefox
  • How to make a tree having multiple type of nodes and each node can have multiple child nodes in java
  • How to recover from a Spring Social ExpiredAuthorizationException
  • Cross-Platform Protobuf Serialization
  • Fill an image in a square container while keeping aspect ratio
  • ILMerge & Keep Assembly Name
  • Large data - storage and query
  • Alternatives to the OPTIONAL fallback SPARQL pattern?
  • Do I've to free mysql result after storing it?
  • Rearranging Cells in UITableView Bug & Saving Changes
  • WOWZA + RTMP + HTML5 Playback?
  • Windows forms listbox.selecteditem displaying “System.Data.DataRowView” instead of actual value
  • Reading document lines to the user (python)
  • How can i traverse a binary tree from right to left in java?