Calculating The Shortest Path Between Any Two Vertices U,v In G

I want to find the set S that contains the shortest path between any two vertices in a graph. The following code is working fine, but I am not sure if there is a more efficient cod

Solution 1:

The efficiency of your current code depends on the implementation of g.get_shortest_paths. Typically choices of g.get_shortest_paths include:

• Bellman–Ford algorithm, which shall run at O(VE),
• Dijkstra's algorithm, which shall run at O(V^2) without optimization, O(Elog(v)) or even O(E+Vlog(E/V)log(V)) if well-optimized.

And the time cost of your code shall be the cost of g.get_shortest_paths times O(V^2) since the iteration.

For all-pairs-shortest-path problem in your case, Floyd–Warshall algorithm is suggested which uses dynamic programming to reach a time cost of O(V^3)

EDITED:

Notations used above: E for number of edges, and V for number of vertices in the graph.

Solution 2:

I implemented the unoptimized Dijkstra's algorithm for a given graph in python some time ago:

def define_undirected_G(): 
   m = 10 #nodes
   G = [set() for _ in range(m)]  #create a set for each node 
                                  #and save the adjacent nodes inside these sets 
   G[0] |= {1,2}
   G[1] |= {0,2,3,4}
   G[2] |= {0,1,4,6,7}
   G[3] |= {1,4}
   G[4] |= {1,2,3,5}
   G[5] |= {4}
return G

---

def dijkstra(G,s): 
       m = len(G) 
       d = [None]*m  #Shortest paths from s to all nodes in G
       d[s] = 0      #Path cost=0 for the startnode
       Q = {u for u in range(m)}   #Q = All nodes u in G
       while Q: # Selection of node with min d-value
           (_,v) = min({(d[u],u) for u in Q if d[u]!= None})
           Q.remove(v) 
           for u in G[v]: #Check Update for all adjacent nodes
               alt = d[v] + G[v][u]   #Greedy-selection-rule            
               if d[u]==None or alt < d[u]:   #Update
                   d[u] = alt 
       return d 

If you want to have a set S containing all shotest paths from all nodes in G, then just calculate dijkstra(G,s) for s in G and add the result to S.

Note: Optimization will be Union Find Data structure and the change of for u in G[v] because there is no need for checking adjacent nodes which were already updated and removed from untouched set of nodes Q because greedy algrotihms are greedy.

Hope this helps.