graphs.breadth_first_search_zero_one_shortest_path

Finding the shortest path in 0-1-graph in O(E + V) which is faster than dijkstra. 0-1-graph is the weighted graph with the weights equal to 0 or 1. Link: https://codeforces.com/blog/entry/22276

Classes

AdjacencyList	Graph adjacency list.
Edge	Weighted directed graph edge.

Module Contents

class graphs.breadth_first_search_zero_one_shortest_path.AdjacencyList(size: int)

Graph adjacency list.

__getitem__(vertex: int) → collections.abc.Iterator[Edge]

Get all the vertices adjacent to the given one.

add_edge(from_vertex: int, to_vertex: int, weight: int)

>>> g = AdjacencyList(2)
>>> g.add_edge(0, 1, 0)
>>> g.add_edge(1, 0, 1)
>>> list(g[0])
[Edge(destination_vertex=1, weight=0)]
>>> list(g[1])
[Edge(destination_vertex=0, weight=1)]
>>> g.add_edge(0, 1, 2)
Traceback (most recent call last):
    ...
ValueError: Edge weight must be either 0 or 1.
>>> g.add_edge(0, 2, 1)
Traceback (most recent call last):
    ...
ValueError: Vertex indexes must be in [0; size).

get_shortest_path(start_vertex: int, finish_vertex: int) → int | None

Return the shortest distance from start_vertex to finish_vertex in 0-1-graph.

1 1 1

0———>3 6——–7>——->8 | ^ ^ ^ |1 | | | |0 v

0| |0 1| 9——–>10

| | ^ 1

v | | |0 1———>2<——-4——->5

0 1 1

>>> g = AdjacencyList(11)
>>> g.add_edge(0, 1, 0)
>>> g.add_edge(0, 3, 1)
>>> g.add_edge(1, 2, 0)
>>> g.add_edge(2, 3, 0)
>>> g.add_edge(4, 2, 1)
>>> g.add_edge(4, 5, 1)
>>> g.add_edge(4, 6, 1)
>>> g.add_edge(5, 9, 0)
>>> g.add_edge(6, 7, 1)
>>> g.add_edge(7, 8, 1)
>>> g.add_edge(8, 10, 1)
>>> g.add_edge(9, 7, 0)
>>> g.add_edge(9, 10, 1)
>>> g.add_edge(1, 2, 2)
Traceback (most recent call last):
    ...
ValueError: Edge weight must be either 0 or 1.
>>> g.get_shortest_path(0, 3)
0
>>> g.get_shortest_path(0, 4)
Traceback (most recent call last):
    ...
ValueError: No path from start_vertex to finish_vertex.
>>> g.get_shortest_path(4, 10)
2
>>> g.get_shortest_path(4, 8)
2
>>> g.get_shortest_path(0, 1)
0
>>> g.get_shortest_path(1, 0)
Traceback (most recent call last):
    ...
ValueError: No path from start_vertex to finish_vertex.

_graph: list[list[Edge]]

_size

property size

class graphs.breadth_first_search_zero_one_shortest_path.Edge

Weighted directed graph edge.

destination_vertex: int

weight: int