Source code for tryalgo.graph01

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Shortest path in a 0,1 weighted graph

jill-jenn vie et christoph durr - 2014-2018
"""

from collections import deque


# snip{
[docs] def dist01(graph, weight, source=0, target=None): """Shortest path in a 0,1 weighted graph :param graph: directed graph in listlist or listdict format :param weight: matrix or adjacency dictionary :param int source: vertex :param target: exploration stops once distance to target is found :returns: distance table, predecessor table :complexity: `O(|V|+|E|)` """ n = len(graph) dist = [float('inf')] * n prec = [None] * n black = [False] * n dist[source] = 0 gray = deque([source]) while gray: node = gray.pop() if black[node]: continue black[node] = True if node == target: break for neighbor in graph[node]: ell = dist[node] + weight[node][neighbor] if black[neighbor] or dist[neighbor] <= ell: continue dist[neighbor] = ell prec[neighbor] = node if weight[node][neighbor] == 0: gray.append(neighbor) else: gray.appendleft(neighbor) return dist, prec
# snip}