From 578f8f5874e66a35660eb0759ef7d90a27fbcffe Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Mon, 5 Jul 2021 15:30:18 -0500 Subject: Dijkstra shortest path done, using heapq. Pretty simple after I first implemented in Java. --- sources/dijkstra.py | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 sources/dijkstra.py (limited to 'sources') diff --git a/sources/dijkstra.py b/sources/dijkstra.py new file mode 100644 index 0000000..e5160d4 --- /dev/null +++ b/sources/dijkstra.py @@ -0,0 +1,45 @@ +# Uses python3 + +import sys +import heapq + + +def distance(adj, cost, s, t): + if s == t: + return 0 + dist = [float('inf')] * len(adj) + visited = [False] * len(adj) + dist[s] = 0 + q = [] + heapq.heappush(q, (dist[s], s)) + + while len(q) != 0: + u = heapq.heappop(q)[1] + if visited[u]: + continue + visited[u] = True + if len(adj[u]) > 0: + for i in range(len(adj[u])): + if dist[adj[u][i]] > dist[u] + cost[u][i]: + dist[adj[u][i]] = dist[u] + cost[u][i] + heapq.heappush(q, (dist[adj[u][i]], adj[u][i])) + + if dist[t] == float('inf'): + return -1 + return dist[t] + + +if __name__ == '__main__': + input = sys.stdin.read() + data = list(map(int, input.split())) + n, m = data[0:2] + data = data[2:] + edges = list(zip(zip(data[0:(3 * m):3], data[1:(3 * m):3]), data[2:(3 * m):3])) + data = data[3 * m:] + adj = [[] for _ in range(n)] + cost = [[] for _ in range(n)] + for ((a, b), w) in edges: + adj[a - 1].append(b - 1) + cost[a - 1].append(w) + s, t = data[0] - 1, data[1] - 1 + print(distance(adj, cost, s, t)) -- cgit v1.2.3