iframe-proxy | Sunbelt Computer Software

History

142 lines (122 loc) · 4.55 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

"""

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

"""

from __future__ import annotations

from collections import deque

from collections.abc import Iterator

from dataclasses import dataclass

@dataclass

class Edge:

"""Weighted directed graph edge."""

destination_vertex: int

weight: int

class AdjacencyList:

"""Graph adjacency list."""

def __init__(self, size: int):

self._graph: list[list[Edge]] = [[] for _ in range(size)]

self._size = size

def __getitem__(self, vertex: int) -> Iterator[Edge]:

"""Get all the vertices adjacent to the given one."""

return iter(self._graph[vertex])

@property

def size(self):

return self._size

def add_edge(self, 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).

"""

if weight not in (0, 1):

raise ValueError("Edge weight must be either 0 or 1.")

if to_vertex < 0 or to_vertex >= self.size:

raise ValueError("Vertex indexes must be in [0; size).")

self._graph[from_vertex].append(Edge(to_vertex, weight))

def get_shortest_path(self, 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)

>>> 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)

>>> g.get_shortest_path(4, 8)

>>> g.get_shortest_path(0, 1)

>>> g.get_shortest_path(1, 0)

Traceback (most recent call last):

...

ValueError: No path from start_vertex to finish_vertex.

"""

queue = deque([start_vertex])

distances: list[int | None] = [None] * self.size

distances[start_vertex] = 0

while queue:

current_vertex = queue.popleft()

current_distance = distances[current_vertex]

if current_distance is None:

continue

for edge in self[current_vertex]:

new_distance = current_distance + edge.weight

dest_vertex_distance = distances[edge.destination_vertex]

if (

isinstance(dest_vertex_distance, int)

and new_distance >= dest_vertex_distance

continue

distances[edge.destination_vertex] = new_distance

if edge.weight == 0:

queue.appendleft(edge.destination_vertex)

else:

queue.append(edge.destination_vertex)

if distances[finish_vertex] is None:

raise ValueError("No path from start_vertex to finish_vertex.")

return distances[finish_vertex]

if __name__ == "__main__":

import doctest

doctest.testmod()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

bfs_zero_one_shortest_path.py

Latest commit

History

bfs_zero_one_shortest_path.py

File metadata and controls