GeezerVison is showing github.com — ClassicComputerScienceProblemsInPython/Chapter4/dijkstra.py at master · tyty999/ClassicComputerScienceProblemsInPython

Expand file tree

dijkstra.py

Copy path

More file actions

Latest commit

History

128 lines (110 loc) · 5.74 KB

dijkstra.py

Copy path

File metadata and controls

128 lines (110 loc) · 5.74 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# dijkstra.py

# From Classic Computer Science Problems in Python Chapter 4

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

# http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

from __future__ import annotations

from typing import TypeVar, List, Optional, Tuple, Dict

from dataclasses import dataclass

from mst import WeightedPath, print_weighted_path

from weighted_graph import WeightedGraph

from weighted_edge import WeightedEdge

from priority_queue import PriorityQueue

V = TypeVar('V') # type of the vertices in the graph

@dataclass

class DijkstraNode:

vertex: int

distance: float

def __lt__(self, other: DijkstraNode) -> bool:

return self.distance < other.distance

def __eq__(self, other: DijkstraNode) -> bool:

return self.distance == other.distance

def dijkstra(wg: WeightedGraph[V], root: V) -> Tuple[List[Optional[float]], Dict[int, WeightedEdge]]:

first: int = wg.index_of(root) # find starting index

# distances are unknown at first

distances: List[Optional[float]] = [None] * wg.vertex_count

distances[first] = 0 # the root is 0 away from the root

path_dict: Dict[int, WeightedEdge] = {} # how we got to each vertex

pq: PriorityQueue[DijkstraNode] = PriorityQueue()

pq.push(DijkstraNode(first, 0))

while not pq.empty:

u: int = pq.pop().vertex # explore the next closest vertex

dist_u: float = distances[u] # should already have seen it

# look at every edge/vertex from the vertex in question

for we in wg.edges_for_index(u):

# the old distance to this vertex

dist_v: float = distances[we.v]

# no old distance or found shorter path

if dist_v is None or dist_v > we.weight + dist_u:

# update distance to this vertex

distances[we.v] = we.weight + dist_u

# update the edge on the shortest path to this vertex

path_dict[we.v] = we

# explore it soon

pq.push(DijkstraNode(we.v, we.weight + dist_u))

return distances, path_dict

# Helper function to get easier access to dijkstra results

def distance_array_to_vertex_dict(wg: WeightedGraph[V], distances: List[Optional[float]]) -> Dict[V, Optional[float]]:

distance_dict: Dict[V, Optional[float]] = {}

for i in range(len(distances)):

distance_dict[wg.vertex_at(i)] = distances[i]

return distance_dict

# Takes a dictionary of edges to reach each node and returns a list of

# edges that goes from `start` to `end`

def path_dict_to_path(start: int, end: int, path_dict: Dict[int, WeightedEdge]) -> WeightedPath:

if len(path_dict) == 0:

return []

edge_path: WeightedPath = []

e: WeightedEdge = path_dict[end]

edge_path.append(e)

while e.u != start:

e = path_dict[e.u]

edge_path.append(e)

return list(reversed(edge_path))

if __name__ == "__main__":

city_graph2: WeightedGraph[str] = WeightedGraph(["Seattle", "San Francisco", "Los Angeles", "Riverside", "Phoenix", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston", "Detroit", "Philadelphia", "Washington"])

city_graph2.add_edge_by_vertices("Seattle", "Chicago", 1737)

city_graph2.add_edge_by_vertices("Seattle", "San Francisco", 678)

city_graph2.add_edge_by_vertices("San Francisco", "Riverside", 386)

city_graph2.add_edge_by_vertices("San Francisco", "Los Angeles", 348)

city_graph2.add_edge_by_vertices("Los Angeles", "Riverside", 50)

city_graph2.add_edge_by_vertices("Los Angeles", "Phoenix", 357)

city_graph2.add_edge_by_vertices("Riverside", "Phoenix", 307)

city_graph2.add_edge_by_vertices("Riverside", "Chicago", 1704)

city_graph2.add_edge_by_vertices("Phoenix", "Dallas", 887)

city_graph2.add_edge_by_vertices("Phoenix", "Houston", 1015)

city_graph2.add_edge_by_vertices("Dallas", "Chicago", 805)

city_graph2.add_edge_by_vertices("Dallas", "Atlanta", 721)

city_graph2.add_edge_by_vertices("Dallas", "Houston", 225)

city_graph2.add_edge_by_vertices("Houston", "Atlanta", 702)

city_graph2.add_edge_by_vertices("Houston", "Miami", 968)

city_graph2.add_edge_by_vertices("Atlanta", "Chicago", 588)

city_graph2.add_edge_by_vertices("Atlanta", "Washington", 543)

city_graph2.add_edge_by_vertices("Atlanta", "Miami", 604)

city_graph2.add_edge_by_vertices("Miami", "Washington", 923)

city_graph2.add_edge_by_vertices("Chicago", "Detroit", 238)

city_graph2.add_edge_by_vertices("Detroit", "Boston", 613)

city_graph2.add_edge_by_vertices("Detroit", "Washington", 396)

city_graph2.add_edge_by_vertices("Detroit", "New York", 482)

city_graph2.add_edge_by_vertices("Boston", "New York", 190)

city_graph2.add_edge_by_vertices("New York", "Philadelphia", 81)

city_graph2.add_edge_by_vertices("Philadelphia", "Washington", 123)

distances, path_dict = dijkstra(city_graph2, "Los Angeles")

name_distance: Dict[str, Optional[int]] = distance_array_to_vertex_dict(city_graph2, distances)

print("Distances from Los Angeles:")

for key, value in name_distance.items():

print(f"{key} : {value}")

print("") # blank line

print("Shortest path from Los Angeles to Boston:")

path: WeightedPath = path_dict_to_path(city_graph2.index_of("Los Angeles"), city_graph2.index_of("Boston"), path_dict)

print_weighted_path(city_graph2, path)