Instantly share code, notes, and snippets.

# romech/levit.py

Last active March 27, 2024 21:24
Show Gist options
• Save romech/34d8a9956afe99d9717746fdfc36c653 to your computer and use it in GitHub Desktop.
Levit's algorithm (also "Pape-Levit's") for finding the shortest paths from one `start` node to all another, Python 3 implementation.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' Levit's algorithm for finding the shortest path from one `start` node to all another. Written according to this article: https://goo.gl/GoeKS5 Doesn't work with negative cycles. See example at the end. ''' from collections import defaultdict, OrderedDict from itertools import chain from math import inf class IndexedQueue(OrderedDict): "Queue-like container with fast search" def push(self, item): self[item] = None def pop(self): return OrderedDict.popitem(self, last=False)[0] "(d,(c,(b,(a,())))) => (a, b, c, d)" restore_path = lambda tup: (*restore_path(tup[1]),tup[0]) if tup else () def levit(gr, start, end=None): ''' `gr` is an adjancety list { u:[(v, cost), ...] | (u,v) ∈ E }, `end` is the desired target node, yet all graph nodes are processed anyway. Returns cost and path if `end` is provided. Else returns costs and paths as dicts. `restore_path(paths[end])` should be used for each desired end node. ''' dist = defaultdict(lambda: inf) dist[start] = 0 path = {start:(start,())} m0 = set() m1, m1_urg = IndexedQueue.fromkeys([start]), IndexedQueue() m2 = set(chain.from_iterable((v for v, _ in from_u) for from_u in gr.values())) - {start} #(u,v)∈E => v∈m2 def relax(u, v, w): if (dist[v] > dist[u] + w): dist[v] = dist[u] + w path[v] = (v, path[u]) return True return False while m1 or m1_urg: u = m1_urg.pop() if m1_urg else m1.pop() for v, c in gr.get(u, ()): if v in m2: m1.push(v) m2.discard(v) relax(u, v, c) elif v in m1: relax(u, v, c) elif v in m0 and relax(u, v, c): m1_urg.push(v) m0.discard(v) m0.add(u) if end is None: return dist, path elif end in path: return dist[end], restore_path(path[end]) else: return inf, () if __name__ == '__main__': edges = [('a', 'b', 1), ('b', 'c', 2), ('c', 'a', 0), ('c', 'd', 1), ('a', '5', 5)] adj_list = defaultdict(list) for u, v, w in edges: adj_list[u].append((v, w)) print(adj_list) cost, path = levit(adj_list, 'a', 'd') print(cost, path) # => 4 ('a', 'b', 'c', 'd') costs, paths = levit(adj_list, 'a') targets = ['b', 'c', 'd'] for t in targets: print(costs[t], restore_path(paths[t]))

### Urmipie commented Mar 27, 2024 • edited Loading

you dont actually need function

`restore_path = lambda tup: (*restore_path(tup[1]),tup[0]) if tup else ()`

for unpacking path tuples
its simpler to just `path[v] = (v, *path[u])` in relax function

`(1, *(2, 3, 4)) == (1, 2, 3, 4)`

to join this conversation on GitHub. Already have an account? Sign in to comment