Source code for tryalgo.a_star

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
Shortest Path algorithm A*.

jill-jênn vie et christoph dürr - 2023

from heapq import heappop, heappush

[docs] def a_star(graph, start, lower_bound): """single source shortest path by A* on an unweighted graph :param graph: iterator on adjacent vertices :param source: source vertex :param lower_bound: lb function on distance to target, must return 0 on target and only there. :returns: distance or -1 (target unreachable) :complexity: `O(|V| + |E|log|V|)` """ closedset = set() openset = set([start]) g = {start: 0 } Q = [(lower_bound(start), start)] while Q: (val, x) = heappop(Q) if lower_bound(x) == 0: return g[x] closedset.add(x) for y in graph(x): if not y in closedset and not y in openset: g[y] = g[x] + 1 val = g[y] + lower_bound(y) heappush(Q, (val, y)) openset.add(y) return -1