CODEWITHSUNDEEP
pythonpython-3.x
Santi Peñate-Vera
Santi Peñate-Vera

Reputation: 1186

accelerate the computation of all possible paths between of combinations of input and output nodes in a graph

I have a problem where I have a graph (representing an electrical network), a list of the source nodes and a list of the drain nodes.

for every drain node, I need to find all the possible paths to every source node.

The trivial solution is:

def get_all_paths(graph, start_list, end_list):
    import progressbar
    progress = progressbar.ProgressBar()

    results = dict()

    for end in progress(end_list):
        paths = list()

        for start in start_list:

            paths.append(find_all_paths(graph, start, end))

        results[end] = paths

    return results

The routine find_all_paths can be found here.

The question is: What can I do to speed up the function find_all_paths? It feels like much information is thrown away when the routine find_all_paths ends and is called again.

Upvotes: 0

Views: 41

Answers (1)

Patrick Kostjens
Patrick Kostjens

Reputation: 5105

You should not calculate all paths for every sink/source node individually. It would be much faster to use an all-pairs shortest path algorithm. I suggest you take a look at the Floyd-Warshall algorithm, for example.

For completion, the pseudo code for the algorithm from Wikipedia:

let dist be a |V| × |V| array of minimum distances initialized to infinity
for each vertex v
  dist[v][v] ← 0
for each edge (u,v)
  dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
  for i from 1 to |V|
    for j from 1 to |V|
      if dist[i][j] > dist[i][k] + dist[k][j] 
        dist[i][j] ← dist[i][k] + dist[k][j]
      end if

Upvotes: 2

Related Questions