0

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.

Community
  • 1
  • 1
Santi Peñate-Vera
  • 1,053
  • 4
  • 33
  • 68

1 Answers1

2

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
Patrick Kostjens
  • 5,065
  • 6
  • 29
  • 46