Graph shortest path Dijkstra - time optimisation #123513
Replies: 2 comments
-
Hi @moroii69 Hmm, I run the code for myself and it ran reasonably quick for large inputs. For One thing that stood out to me was the excessive use of lists. If you have a lot of lookups, you should use tuples for this. They cannot be altered but are faster. I used this technique for the graph by converting it to tuples after building the graph. However, the algorithm terminates so early (at least with random data) that the cost of converting is higher than the reduced cost of lookup. Maybe try this with the testcases your course gives you. It may be handcrafted to maximize the number of iterations. |
Beta Was this translation helpful? Give feedback.
-
Hi @moroii69 ✋ import sys
import heapq
def dijkstra(graph, start, end):
n = len(graph)
distances = [float('inf')] * n
distances[start] = 0
prev = [-1] * n
pq = [(0, start)]
while pq:
dist, u = heapq.heappop(pq)
if u == end:
path = [end]
while prev[path[-1]] != -1:
path.append(prev[path[-1]])
path.reverse()
return dist, path
for v, w in graph[u]:
if dist + w < distances[v]:
distances[v] = dist + w
prev[v] = u
heapq.heappush(pq, (distances[v], v))
return -1, []
input_data = sys.stdin.read().split()
index = 0
n, m = int(input_data[index]), int(input_data[index+1])
index += 2
graph = [[] for _ in range(n)]
for _ in range(m):
v, u, w = int(input_data[index]), int(input_data[index+1]), int(input_data[index+2])
graph[v-1].append((u-1, w))
graph[u-1].append((v-1, w))
index += 3
distance, path = dijkstra(graph, 0, n-1)
if distance == -1:
sys.stdout.write("-1\n")
else:
sys.stdout.write(str(len(path)) + "\n")
sys.stdout.write(" ".join(str(x+1) for x in path) + "\n") |
Beta Was this translation helpful? Give feedback.
-
algorithm course progress
currently, I'm progressing through my Algorithm course.
input data
the input data consists of two numbers:
the following 𝑚 lines describe the roads between the settlements. each road is described by three numbers:
output
the output should contain:
time limit: 1 second
memory limit per test: 256 megabytes
python implementation
the algorithm works right, but i have problems with time limit. i have already made an optimization which works x2 faster from the one i have started with, but there are much more optimization ahead.
i have researched for about 10 days and read already a lot staff on this topic, but either i don't understand how to implement, or its just optimization
i have chosen dijkstra algorithm as a classic way to solve this kind of problems.
after researching ways of realizations, I have chosen heap as the fastest recommended. Also tried another ways to collect the path.
also changed input output to sys.stdout and have some benefits at speed but still not enough * maybe there is a better algorithm for his task? or its just the problem of not proper optimization?
guidelines
Beta Was this translation helpful? Give feedback.
All reactions