My code takes a long time for big graphs.
How can I make it faster?
I'm trying to calculate the shortest path for 3 path's using queue but for big input my program crashes.
I'm stuck here. Can someone help me?
def bfs(graph, start, end):
queue = []
queue.append([start])
while queue:
path = queue.pop(0)
node = path[-1]
if node == end:
return len(path)
for adjacent in graph.get(node, []):
new_path = list(path)
new_path.append(adjacent)
queue.append(new_path)
def all_possiblities():
possiblites = []
for clinique in cliniques[0][1:]:
for clinique2 in cliniques[1][1:]:
path1 = bfs(sorted_connections, a, clinique)
path2 = bfs(sorted_connections, clinique, clinique2)
path3 = bfs(sorted_connections, clinique2, b)
total_path = path1 + path2 + path3
possiblites.append(total_path)
return min(possiblites) - 2
if __name__ == '__main__':
input_values = input().split()
n, m = int(input_values[0]), int(input_values[1])
a, b = int(input_values[2]), int(input_values[3])
connections = [list(map(int, input().split())) for _ in range(m)]
cliniques = [list(map(int, input().split())) for _ in range(m, m+2)]
sorted_connections = {}
for road in connections:
city1, city2 = road
sorted_connections.setdefault(city1, []).append(city2)
sorted_connections.setdefault(city2, []).append(city1)
print(all_possiblities())
Input:
10 12 4 6
0 1
1 2
2 7
7 6
6 9
9 8
8 4
4 3
3 0
5 1
5 4
5 6
2 0 2
2 8 9
Output:
8
-
3\$\begingroup\$ As we all want to make our code more efficient or improve it in one way or another, try to write a title that summarizes what your code does, not what you want to get out of a review. Please see How to get the best value out of Code Review - Asking Questions for guidance on writing good question titles. \$\endgroup\$BCdotWEB– BCdotWEB2016年06月13日 09:46:08 +00:00Commented Jun 13, 2016 at 9:46
-
\$\begingroup\$ Can you provide an example of input? \$\endgroup\$N3buchadnezzar– N3buchadnezzar2016年06月13日 09:53:52 +00:00Commented Jun 13, 2016 at 9:53
-
\$\begingroup\$ I updated my question with example \$\endgroup\$Joe– Joe2016年06月13日 09:57:29 +00:00Commented Jun 13, 2016 at 9:57
-
2\$\begingroup\$ @Joe: Is this a programming challenge? If so, can you link to the original problem description? \$\endgroup\$Gareth Rees– Gareth Rees2016年06月13日 10:19:51 +00:00Commented Jun 13, 2016 at 10:19
1 Answer 1
The key reasons for the poor performance are:
Representing
queue
as a list. This is slow because popping an item off the beginning of a list takes time proportional to the length of the list.What you need here is a
collections.deque
.Computing shortest distances many times over. The shortest distance from
a
toclinique
is computed again for everyclinique2
, even though it will be the same each time. Similarly, the shortest distance fromclinique2
tob
is computed again for everyclinique
.What you need here is to compute these distances once and remember them.
If the number of cliniques is large compared with the number of cities, you should use the Floyd–Warshall algorithm to compute distances between all pairs of cities in one go (instead of using Dijkstra's algorithm many times, as in the posted code).
If I were implementing this, I'd use scipy.sparse.csgraph.floyd_warshall
and write:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
def shortest_distance_via(graph, a, b, c1, c2):
"""Return the shortest distance in graph from a to b via C1 and C2 (in
that order), where C1 and C2 are nodes in c1 and c2 respectively.
Arguments:
graph -- NxN array of distances between nodes.
a, b -- nodes in the graph.
c1, c2 -- arrays of nodes in the graph.
"""
d = floyd_warshall(graph)
ab = d[a, c1, np.newaxis] + d[np.meshgrid(c1, c2)] + d[np.newaxis, c2, b]
return ab.min()
-
\$\begingroup\$ how can i avoid counting the shortest path many times in my code? \$\endgroup\$Joe– Joe2016年06月13日 10:47:25 +00:00Commented Jun 13, 2016 at 10:47
-
\$\begingroup\$ using breath first search? \$\endgroup\$Joe– Joe2016年06月13日 10:48:03 +00:00Commented Jun 13, 2016 at 10:48
-
1\$\begingroup\$ @Joe: Compute each path once and remember it! \$\endgroup\$Gareth Rees– Gareth Rees2016年06月13日 10:55:08 +00:00Commented Jun 13, 2016 at 10:55