Calculate the shortest route of a graph with Dijkstra's algorithm and Python
TL;DR
--Learn about Dijkstra's algorithm for calculating the shortest route in a graph. ――We will also touch on the very basic terms used in graph theory. ――Actually write Dijkstra's algorithm in Python to deepen your understanding.
Explanation of graphs and simple terms targeted this time
This time, we will deal with the following graphs. Imagine something like a station map.
Parts such as A and B are called vertices or nodes. In terms of the route map, it is a station that stops.
The part of the line connecting each vertex is called an edge or edge / branch. In terms of the route map, it corresponds to the line connecting stations.
The numbers on the edges are called weights and costs. It will be the cost required to pass through that edge. In terms of the route map, it corresponds to the distance between stations. In this article, we will deal with the distance between vertices.
In addition, there are two types of graphs: undirected graphs and directed graphs. The direction of the undirected graph is not fixed between the vertices. You can proceed in both directions. Speaking of the route map, it's like going up and down at a certain station. Directed graphs, on the other hand, can only move in one direction between vertices. This article deals with the contents of undirected graphs.
What is Dijkstra's algorithm?
Dijkstra's Algorithm Dijkstra's Algorithm is a graph theory algorithm for calculating the shortest path of a graph.
The algorithm calculates how to go from one vertex to another vertex to get the shortest distance.
The content is similar to the A \ * algorithm mentioned in the article I wrote a while ago (Writing an A \ * (A-star) algorithm in Python). (Although there are differences such as heuristics).
The problem to be solved with Python this time
Calculate the shortest path from vertex A to vertex J in Python in the graph below, which I mentioned a while ago.
Calculation contents of Dijkstra method
-[1]. Determine the starting apex. -[2]. Stores the distance from the start vertex to the vertex adjacent to that vertex in a list or the like. -It also holds a reference to the edge that led to the adjacent vertex. -[3]. Next, move to the adjacent vertex and store the distance from the starting vertex to the vertex adjacent to that vertex. --At that time, if the distance from the start vertex of the adjacent vertex is already stored (if the distance to the target vertex is calculated by another route), it is stored only when the distance becomes short. Update the value of the distance you are. --When the distance is updated, the reference of the edge to the vertex held in [2] is also updated. -Repeat [4]. [3] and repeat the calculation until there are no more targets (calculation of all routes is completed).
After the calculation is completed, if you want to find the shortest distance from the start vertex to any vertex, each vertex retains the reference to the edge immediately before it is the shortest to reach that vertex, so the final The shortest path can be obtained by referring to the edges in order from the apex of the goal, tracing the apex to the apex of the start, and inverting the route.
It's hard to understand if it's just letters, so I'll touch it with a little figure. First is the [1] and [2] parts.
The part in red is the distance calculated by the calculation iteration. First, we will start from the top of A.
It is natural from the vertex of A to the vertex of A, but the distance is 0. Hold the distance and the edge to that vertex at the vertices B and E adjacent to A required in [2].
At this stage, the distance between the vertices of the target B and E has not been calculated by other paths yet, so this value is retained as it is. At this point, the shortest distance to the apex of B is 80 and the shortest distance to the apex of E is 200.
It also stores the information of the edge immediately before the shortest distance (this time, the edge between A and B and the edge between A and E).
Next, as the calculation of [3], move the object to the vertex of B. Since there are four vertices A, C, D, and E adjacent to the vertices of B, calculations are performed for each of them.
First of all, the distance from B to A, which is calculated to return by the route. Originally, the distance from A to A was set to 0, so the route A → B → A has a distance of 80 + 80, which is 160. Since this distance is greater than 0, we will not update the distance or edge references.
Similarly, for the route from B to E, the distance is 290, which is already greater than the distance of 200 for the route from A to E, so it does not update the shortest distance and edge references.
Since the distances from B to C and B to D have not yet been calculated from another route, they will be newly adopted and retained as the shortest distances.
When the calculation of the vertex of B is completed in step [3], it becomes as follows.
In this way, the target vertices are shifted in order, and the update is repeated when the distance to the adjacent vertex has not been calculated yet or the shortest distance becomes shorter. The updated adjacent vertices are added to the queue later as the target vertices for calculation.
What to use in Python implementation
- Python 3.8.5
Implementation in Python
First, import the required modules. Since type annotation is used, add annotations and each class of typing package. Also, since the priority queue is used to control the vertices to be targeted in Dijkstra's calculation (I feel like I can use a normal queue without using it), I am loading the one in the heapq package. ..
from __future__ import annotations
from typing import Tuple, List, Optional, Dict
from heapq import heappush, heappop
Next, we will define constants for vertices. VertexStr is a simple str type alias. If you abuse it, it may be difficult to distinguish it from the class, but it is convenient to make it easy to understand that "this argument is a string of vertex constants", so I will use it this time.
VertexStr = str
class Vertex:
"""A class that handles constants in the string that represents each vertex.
"""
A: VertexStr = 'A'
B: VertexStr = 'B'
C: VertexStr = 'C'
D: VertexStr = 'D'
E: VertexStr = 'E'
F: VertexStr = 'F'
G: VertexStr = 'G'
H: VertexStr = 'H'
I: VertexStr = 'I'
J: VertexStr = 'J'
K: VertexStr = 'K'
Next, we will define a class for the edge. The vertex information and the weight (distance in this case) at that edge are stored in the attribute (for determining which vertex is the edge to connect to which vertex).
class Edge:
def __init__(
self, from_idx: int, to_idx: int,
from_vertex: VertexStr, to_vertex: VertexStr,
weight: float) -> None:
"""
A class that handles a single edge.
Parameters
----------
from_idx : int
Index of the vertex of the connection source.
to_idx : int
Index of the vertex to connect to.
weight : float
Edge weight.
"""
self.from_idx: int = from_idx
self.to_idx: int = to_idx
self.from_vertex: VertexStr = from_vertex
self.to_vertex: VertexStr = to_vertex
self.weight: float = weight
In the edge addition process, add a method for inversion because it is convenient to add the one whose direction is inverted (for example, generate the edge of vertex A → vertex B from the edge of vertex B → vertex A).
def reversed(self) -> Edge:
"""
Get the edge where the connection source and connection destination of the vertex are inverted.
Returns
-------
reversed_edge : Edge
Edges with inverted source and destination vertices.
"""
reversed_edge = Edge(
from_idx=self.to_idx,
to_idx=self.from_idx,
from_vertex=self.from_vertex,
to_vertex=self.to_vertex,
weight=self.weight)
return reversed_edge
Also, adjust the contents when the instance of this class is output by the print function etc. so that it will be convenient when outputting the route later. The output will be as follows.
from: A(weight: 80) -> to: B
def __str__(self) -> str:
"""
Convert edge information to a character string.
Returns
-------
edge_info_str : str
A string of converted edge information.
"""
edge_info_str: str = (
f'from: {self.from_vertex}'
f'(weight: {self.weight})'
f' -> to: {self.to_vertex}'
)
return edge_info_str
Next, we will define a class for the graph. For the vertices argument, specify a list of values of the Vertex class constants later, such as ʻA, B, C ...
A multidimensional list is created by looping the attribute _edges as many times as there are vertices. The second dimension stores multiple edges connected to the target vertex. The edges are still empty at this point, but we'll add them later.
class Graph:
def __init__(self, vertices: List[VertexStr]) -> None:
"""
A class for working with graphs.
Parameters
----------
vertices : list of str
A list of vertex strings.
"""
self._vertices: List[VertexStr] = vertices
self._edges: List[List[Edge]] = []
for _ in vertices:
self._edges.append([])
We will add each method required for some calculations. The first is the method to get the vertex of the target index position.
def vertex_at(self, index: int) -> VertexStr:
"""
Gets the string of vertices at the specified index.
Parameters
----------
index : int
Target index.
Returns
-------
vertex_str : str
A string of vertices at the target index position.
"""
return self._vertices[index]
Conversely, add a method to get the corresponding index from the vertex string.
def index_of(self, vertex: VertexStr) -> int:
"""
Get the intex of the target vertex.
Parameters
----------
vertex : str
A character string for identifying the target vertex.
Returns
-------
index : int
Index of the target vertex.
"""
return self._vertices.index(vertex)
Add a method as a property of how many vertices there are.
@property
def vertex_count(self):
"""
Attribute value of the set number of vertices.
Returns
-------
vertex_count : int
The number of vertices that have been set.
"""
return len(self._vertices)
Add a method to get a list of edges connected to the vertices of the target index position.
def edges_at(self, vertex_index: int) -> List[Edge]:
"""
Of the edge set at the vertex of the specified index position
Get the list.
Parameters
----------
vertex_index : int
Index of the target vertex position.
Returns
-------
edges : list of Edge
A list of edges set for the vertices of interest.
"""
return self._edges[vertex_index]
Adds processing to get a list of vertices adjacent to the specified vertex and tuples that store the weights of their edges. It is used in the calculation to calculate the adjacent vertices when the shortest distance is calculated for a specific vertex.
def get_neighbor_vertices_and_weights_by_index(
self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
"""
Connected to the vertices of the specified index with an edge
Get a list of tuples of weight values for vertices and their edges.
Parameters
----------
vertex_index : int
Index of the target vertex.
Returns
-------
neighbor_vertices_and_weights : list of tuple
A list containing tuples of calculated vertices and their edge weights.
"""
neighbor_vertices_and_weights: List[Tuple[VertexStr, float]] = []
for edge in self.edges_at(vertex_index=vertex_index):
tuple_val = (
self.vertex_at(index=edge.to_idx),
edge.weight,
)
neighbor_vertices_and_weights.append(tuple_val)
return neighbor_vertices_and_weights
Add a method to add edges to the graph. We also want to add edges in the opposite direction to reduce the description. For example, if an edge in the direction of A → B is added, an edge in the direction of B → A is also added. To generate a flipped edge, use the reversed method added to the Edge class.
def add_edge(self, edge: Edge) -> None:
"""
Add edges to the graph.
Notes
-----
Inverted edges are also added to the connected vertices (edges are
A total of 2 items will be added by executing the method).
Parameters
----------
edge : Edge
The edge to be added.
"""
self._edges[edge.from_idx].append(edge)
self._edges[edge.to_idx].append(edge.reversed())
It also adds a method that then adds edges according to the characters at the two specified vertices. This allows you to write something like "add an edge between A and B". Since the add_edge method is called internally, the edge in the opposite direction is also added (inverted form).
At the end of the graph class, the information of the vertices added at the time of printing etc. and the adjacent vertices (and edges) set for those vertices should be output. The output will be as follows.
Graph information:
Vertex of interest: A ->Adjacent vertex data: [('B', 80), ('E', 200)]
Vertex of interest: B ->Adjacent vertex data: [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
...
def __str__(self) -> str:
"""
Return the character string of graph information.
Returns
-------
graph_info : str
A string of graph information.
"""
graph_info: str = ''
for index in range(self.vertex_count):
neighbors_data = self.get_neighbor_vertices_and_weights_by_index(
vertex_index=index)
graph_info += (
f'Vertex of interest: {self.vertex_at(index=index)}'
f' ->Adjacent vertex data: {neighbors_data}\n'
)
return graph_info
Next, add a class that handles the distance from the start vertex to a specific vertex by Dijkstra's algorithm, and describes the processing for calculating the weight (distance).
class DijkstraDistanceVertex:
def __init__(self, vertex_idx: int, distance: float) -> None:
"""
Distance (weight) from the start vertex of a particular vertex for Dijkstra's algorithm
A class for comparison control with other vertices.
Parameters
----------
vertex : str
Index for identifying the target vertex.
distance : float
Distance from the top of the start.
"""
self.vertex_idx = vertex_idx
self.distance = distance
Add a method for weight comparison. Dijkstra's algorithm is used to determine if the route to a vertex that has already been calculated will be shorter after the calculation.
def __lt__(self, other: DijkstraDistanceVertex) -> bool:
"""
Acquires the truth value of the comparison result of the distance (weight) of other vertices.
Parameters
----------
other : DijkstraDistanceVertex
The vertices to be compared.
Returns
-------
result : bool
If True and the lesser condition is met.
"""
return self.distance < other.distance
def __eq__(self, other: DijkstraDistanceVertex) -> bool:
"""
The boolean value of whether the distance (weight) with other vertices matches.
get.
Parameters
----------
other : DijkstraDistanceVertex
The vertices to be compared.
Returns
-------
result : bool
If True and the match condition is met.
"""
return self.distance == other.distance
Next is the preparation of the priority queue class. Each time the shortest distance to each vertex is updated, that vertex is added to the queue. After all, the calculation is done for all, so it was okay to queue normally even if it was not prioritized ...? I don't feel like it.
class PriorityQueue:
def __init__(self) -> None:
"""
A class that handles priority queues.
"""
self._container: List[DijkstraDistanceVertex] = []
@property
def empty(self) -> bool:
"""
Boolean attribute of whether the queue is empty.
Returns
-------
result : bool
True is set if the queue is empty.
"""
return not self._container
def push(self, item: DijkstraDistanceVertex) -> None:
"""
Handle the distance from the start of a specific vertex of Dijkstra's algorithm to the queue
Add an instance.
Parameters
----------
item : DijkstraDistanceVertex
The instance to be added.
"""
heappush(self._container, item)
def pop(self) -> DijkstraDistanceVertex:
"""
Extract one instance according to the priority from the queue.
Returns
-------
item : DijkstraDistanceVertex
The retrieved instance.
"""
return heappop(self._container)
Now that the graphs are ready, let's write the Dijkstra calculation.
def dijkstra(
graph: Graph,
root_vertex: VertexStr
) -> tuple[List[Optional[float]], Dict[int, Edge]]:
"""
Dijkstra's algorithm is used to determine the distance for each vertex and the shortest route to each vertex.
Calculate the path.
Parameters
----------
graph : Graph
Target graph.
root_vertex : str
A character string for identifying the vertex of the position where the search is started.
Returns
-------
distances : list of float
The distance from the vertex of the search start position of each vertex.
path_dict : dict
The key is the index of the target vertex, and the value is the vertex.
Stores the immediately preceding edge of the shortest route.
"""
first_idx: int = graph.index_of(vertex=root_vertex)
distances: List[Optional[float]] = [
None for _ in range(graph.vertex_count)]
distances[first_idx] = 0
path_dict: Dict[int, Edge] = {}
priority_queue: PriorityQueue = PriorityQueue()
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=first_idx,
distance=0))
while not priority_queue.empty:
from_idx:int = priority_queue.pop().vertex_idx
from_vertex_distance: float = distances[from_idx]
for edge in graph.edges_at(vertex_index=from_idx):
#Already set to the target vertex before the target iteration
#Get the distance (value set by another route, etc.).
to_distance: Optional[float] = distances[edge.to_idx]
#Calculate the distance on this route.
current_route_distance: float = edge.weight + from_vertex_distance
#If the distance on another route has already been set, and on this route
#If the distance is not shorter, the update process is skipped.
if (to_distance is not None
and to_distance <= current_route_distance):
continue
distances[edge.to_idx] = current_route_distance
path_dict[edge.to_idx] = edge
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=edge.to_idx,
distance=current_route_distance))
return distances, path_dict
For the argument root_vertex, we want to give the shortest path from A to J this time, so specify A later.
while not priority_queue.empty:
And so on, the processing is continued with the while statement until the vertex to be searched disappears from the queue.
to_distance: Optional[float] = distances[edge.to_idx]
In the while statement, the past value (value already calculated by another route) is acquired for the distance to the vertex to be calculated. At first, None is set, so if it is the first vertex, it will be None.
current_route_distance: float = edge.weight + from_vertex_distance
Calculates the current distance of a while statement. The weight (distance) of the immediately preceding edge and the distance to the immediately preceding vertex are added together.
if (to_distance is not None
and to_distance <= current_route_distance):
continue
If the distance calculated by another route already exists and the distance calculated by this iteration does not become shorter, updating is unnecessary and the process is skipped.
distances[edge.to_idx] = current_route_distance
path_dict[edge.to_idx] = edge
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=edge.to_idx,
distance=current_route_distance))
If the distance is shortened, or if it is the first vertex to be calculated, update the distance to that vertex, update the information on the edge immediately before the shortest distance to that vertex, and calculate that vertex in a later iteration. Add to the queue.
return distances, path_dict
The return value is a list that stores information on the shortest distance to each vertex and a dictionary that stores the edge immediately before the route that is the shortest distance to each vertex.
Next, prepare a function to obtain the shortest path from the start vertex to any final vertex from the dictionary that stores the edge immediately before the calculated shortest path of each vertex.
As mentioned above in the calculation method, the node immediately before the shortest distance is traced in order from the last vertex (J this time), and the edge is added to the list. Stop the loop when you reach the top of the start. Also, before returning it, invert it with the revese method so that the order is from the start vertex to the last vertex.
def to_route_path_from_path_dict(
start_vertex_idx: int,
last_vertex_idx: int,
path_dict: Dict[int, Edge]) -> RoutePath:
"""
Using a dictionary that stores the edge just before the shortest distance to reach that path,
The shortest distance to the specified vertex
Parameters
----------
start_vertex_idx : int
The apex that is the starting point of the route you want to find
last_vertex_idx : int
The index of the vertices that are the final points of the route you want to find.
path_dict : dict
The key is the index of the target vertex, and the value is the shortest path to that vertex.
A dictionary containing the previous edge.
"""
route_path: RoutePath = []
current_edge: Edge = path_dict[last_vertex_idx]
route_path.append(current_edge)
while current_edge.from_idx != start_vertex_idx:
current_edge = path_dict[current_edge.from_idx]
route_path.append(current_edge)
route_path.reverse()
return route_path
Finally, use the prepared one to instantiate the graph, add nodes, etc., and output the calculation and calculation result to complete.
if __name__ == '__main__':
graph = Graph(
vertices=[
Vertex.A,
Vertex.B,
Vertex.C,
Vertex.D,
Vertex.E,
Vertex.F,
Vertex.G,
Vertex.H,
Vertex.I,
Vertex.J,
Vertex.K,
])
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.B,
weight=80)
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.E,
weight=200)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.C,
weight=92)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.D,
weight=83)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.E,
weight=210)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.D,
weight=43)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.E,
weight=93)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.F,
weight=66)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.G,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.H,
weight=123)
graph.add_edge_by_vertices(
from_vertex=Vertex.E,
to_vertex=Vertex.F,
weight=81)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.G,
weight=46)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.K,
weight=100)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.H,
weight=141)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.I,
weight=53)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.K,
weight=112)
graph.add_edge_by_vertices(
from_vertex=Vertex.H,
to_vertex=Vertex.I,
weight=86)
graph.add_edge_by_vertices(
from_vertex=Vertex.I,
to_vertex=Vertex.J,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.J,
to_vertex=Vertex.K,
weight=92)
print('-' * 20)
print('Graph information:')
print(graph)
print('-' * 20)
distances, path_dict = dijkstra(
graph=graph,
root_vertex=Vertex.A)
print('Shortest distance information from the calculated vertex A to each vertex:')
for index, distance in enumerate(distances):
vertex: VertexStr = graph.vertex_at(index=index)
print('vertex:', vertex, 'distance:', distance)
print('-' * 20)
start_vertex_idx = graph.index_of(vertex=Vertex.A)
last_vertex_idx = graph.index_of(vertex=Vertex.J)
route_path: RoutePath = to_route_path_from_path_dict(
start_vertex_idx=start_vertex_idx,
last_vertex_idx=last_vertex_idx,
path_dict=path_dict)
print('Shortest path from vertex A to vertex J:')
for edge in route_path:
print(edge)
The graph information is output as follows.
Graph information:
Vertex of interest: A ->Adjacent vertex data: [('B', 80), ('E', 200)]
Vertex of interest: B ->Adjacent vertex data: [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
Vertex of interest: C ->Adjacent vertex data: [('B', 92), ('D', 43), ('E', 93), ('F', 66)]
Vertex of interest: D ->Adjacent vertex data: [('B', 83), ('C', 43), ('G', 95), ('H', 123)]
Vertex of interest: E ->Adjacent vertex data: [('A', 200), ('B', 210), ('C', 93), ('F', 81)]
Vertex of interest: F ->Adjacent vertex data: [('C', 66), ('E', 81), ('G', 46), ('K', 100)]
Vertex of interest: G ->Adjacent vertex data: [('D', 95), ('F', 46), ('H', 141), ('I', 53), ('K', 112)]
Vertex of interest: H ->Adjacent vertex data: [('D', 123), ('G', 141), ('I', 86)]
Vertex of interest: I ->Adjacent vertex data: [('G', 53), ('H', 86), ('J', 95)]
Vertex of interest: J ->Adjacent vertex data: [('I', 95), ('K', 92)]
Vertex of interest: K ->Adjacent vertex data: [('F', 100), ('G', 112), ('J', 92)]
The shortest distance to each vertex is output as follows.
Shortest distance information from the calculated vertex A to each vertex:
vertex:A distance: 0
vertex:B distance: 80
vertex:C distance: 172
vertex:D distance: 163
vertex:E distance: 200
vertex:F distance: 238
vertex:G distance: 258
vertex:H distance: 286
vertex:I distance: 311
vertex:J distance: 406
vertex:K distance: 338
And the shortest route was calculated as A → B → D → G → I → J.
Shortest path from vertex A to vertex J:
from: A(weight: 80) -> to: B
from: B(weight: 83) -> to: D
from: D(weight: 95) -> to: G
from: G(weight: 53) -> to: I
from: I(weight: 95) -> to: J
Looking at the image of the graph, it surely seems to fit.
Digression
Originally I graduated from a school in the design field, so please forgive Masakari who is strong in the knowledge of computer science.
Whole code
from __future__ import annotations
from typing import Tuple, List, Optional, Dict
from heapq import heappush, heappop
VertexStr = str
class Vertex:
"""A class that handles constants in the string that represents each vertex.
"""
A: VertexStr = 'A'
B: VertexStr = 'B'
C: VertexStr = 'C'
D: VertexStr = 'D'
E: VertexStr = 'E'
F: VertexStr = 'F'
G: VertexStr = 'G'
H: VertexStr = 'H'
I: VertexStr = 'I'
J: VertexStr = 'J'
K: VertexStr = 'K'
class Edge:
def __init__(
self, from_idx: int, to_idx: int,
from_vertex: VertexStr, to_vertex: VertexStr,
weight: float) -> None:
"""
A class that handles a single edge.
Parameters
----------
from_idx : int
Index of the vertex of the connection source.
to_idx : int
Index of the vertex to connect to.
weight : float
Edge weight.
"""
self.from_idx: int = from_idx
self.to_idx: int = to_idx
self.from_vertex: VertexStr = from_vertex
self.to_vertex: VertexStr = to_vertex
self.weight: float = weight
def reversed(self) -> Edge:
"""
Get the edge where the connection source and connection destination of the vertex are inverted.
Returns
-------
reversed_edge : Edge
Edges with inverted source and destination vertices.
"""
reversed_edge = Edge(
from_idx=self.to_idx,
to_idx=self.from_idx,
from_vertex=self.from_vertex,
to_vertex=self.to_vertex,
weight=self.weight)
return reversed_edge
def __str__(self) -> str:
"""
Convert edge information to a character string.
Returns
-------
edge_info_str : str
A string of converted edge information.
"""
edge_info_str: str = (
f'from: {self.from_vertex}'
f'(weight: {self.weight})'
f' -> to: {self.to_vertex}'
)
return edge_info_str
class Graph:
def __init__(self, vertices: List[VertexStr]) -> None:
"""
A class for working with graphs.
Parameters
----------
vertices : list of str
A list of vertex strings.
"""
self._vertices: List[VertexStr] = vertices
self._edges: List[List[Edge]] = []
for _ in vertices:
self._edges.append([])
def vertex_at(self, index: int) -> VertexStr:
"""
Gets the string of vertices at the specified index.
Parameters
----------
index : int
Target index.
Returns
-------
vertex_str : str
A string of vertices at the target index position.
"""
return self._vertices[index]
def index_of(self, vertex: VertexStr) -> int:
"""
Get the intex of the target vertex.
Parameters
----------
vertex : str
A character string for identifying the target vertex.
Returns
-------
index : int
Index of the target vertex.
"""
return self._vertices.index(vertex)
@property
def vertex_count(self):
"""
Attribute value of the set number of vertices.
Returns
-------
vertex_count : int
The number of vertices that have been set.
"""
return len(self._vertices)
def edges_at(self, vertex_index: int) -> List[Edge]:
"""
Of the edge set at the vertex of the specified index position
Get the list.
Parameters
----------
vertex_index : int
Index of the target vertex position.
Returns
-------
edges : list of Edge
A list of edges set for the vertices of interest.
"""
return self._edges[vertex_index]
def get_neighbor_vertices_and_weights_by_index(
self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
"""
Connected to the vertices of the specified index with an edge
Get a list of tuples of weight values for vertices and their edges.
Parameters
----------
vertex_index : int
Index of the target vertex.
Returns
-------
neighbor_vertices_and_weights : list of tuple
A list containing tuples of calculated vertices and their edge weights.
"""
neighbor_vertices_and_weights: List[Tuple[VertexStr, float]] = []
for edge in self.edges_at(vertex_index=vertex_index):
tuple_val = (
self.vertex_at(index=edge.to_idx),
edge.weight,
)
neighbor_vertices_and_weights.append(tuple_val)
return neighbor_vertices_and_weights
def add_edge(self, edge: Edge) -> None:
"""
Add edges to the graph.
Notes
-----
Inverted edges are also added to the connected vertices (edges are
A total of 2 items will be added by executing the method).
Parameters
----------
edge : Edge
The edge to be added.
"""
self._edges[edge.from_idx].append(edge)
self._edges[edge.to_idx].append(edge.reversed())
def add_edge_by_vertices(
self, from_vertex: VertexStr,
to_vertex: VertexStr,
weight: float) -> None:
"""
Adds an edge between the two specified vertices.
Parameters
----------
from_vertex : str
Specify the vertex of the connection source.
to_vertex : str
Specify the vertex to connect to.
weight : float
Edge weight value.
"""
from_idx = self._vertices.index(from_vertex)
to_idx = self._vertices.index(to_vertex)
edge = Edge(
from_idx=from_idx,
to_idx=to_idx,
from_vertex=from_vertex,
to_vertex=to_vertex,
weight=weight)
self.add_edge(edge=edge)
def __str__(self) -> str:
"""
Return the character string of graph information.
Returns
-------
graph_info : str
A string of graph information.
"""
graph_info: str = ''
for index in range(self.vertex_count):
neighbors_data = self.get_neighbor_vertices_and_weights_by_index(
vertex_index=index)
graph_info += (
f'Vertex of interest: {self.vertex_at(index=index)}'
f' ->Adjacent vertex data: {neighbors_data}\n'
)
return graph_info
class DijkstraDistanceVertex:
def __init__(self, vertex_idx: int, distance: float) -> None:
"""
Distance (weight) from the start vertex of a particular vertex for Dijkstra's algorithm
A class for comparison control with other vertices.
Parameters
----------
vertex : str
Index for identifying the target vertex.
distance : float
Distance from the top of the start.
"""
self.vertex_idx = vertex_idx
self.distance = distance
def __lt__(self, other: DijkstraDistanceVertex) -> bool:
"""
Acquires the truth value of the comparison result of the distance (weight) of other vertices.
Parameters
----------
other : DijkstraDistanceVertex
The vertices to be compared.
Returns
-------
result : bool
If True and the lesser condition is met.
"""
return self.distance < other.distance
def __eq__(self, other: DijkstraDistanceVertex) -> bool:
"""
The boolean value of whether the distance (weight) with other vertices matches.
get.
Parameters
----------
other : DijkstraDistanceVertex
The vertices to be compared.
Returns
-------
result : bool
If True and the match condition is met.
"""
return self.distance == other.distance
class PriorityQueue:
def __init__(self) -> None:
"""
A class that handles priority queues.
"""
self._container: List[DijkstraDistanceVertex] = []
@property
def empty(self) -> bool:
"""
Boolean attribute of whether the queue is empty.
Returns
-------
result : bool
True is set if the queue is empty.
"""
return not self._container
def push(self, item: DijkstraDistanceVertex) -> None:
"""
Handle the distance from the start of a specific vertex of Dijkstra's algorithm to the queue
Add an instance.
Parameters
----------
item : DijkstraDistanceVertex
The instance to be added.
"""
heappush(self._container, item)
def pop(self) -> DijkstraDistanceVertex:
"""
Extract one instance according to the priority from the queue.
Returns
-------
item : DijkstraDistanceVertex
The retrieved instance.
"""
return heappop(self._container)
def dijkstra(
graph: Graph,
root_vertex: VertexStr
) -> tuple[List[Optional[float]], Dict[int, Edge]]:
"""
Dijkstra's algorithm is used to determine the distance for each vertex and the shortest route to each vertex.
Calculate the path.
Parameters
----------
graph : Graph
Target graph.
root_vertex : str
A character string for identifying the vertex of the position where the search is started.
Returns
-------
distances : list of float
The distance from the vertex of the search start position of each vertex.
path_dict : dict
The key is the index of the target vertex, and the value is the vertex.
Stores the immediately preceding edge of the shortest route.
"""
first_idx: int = graph.index_of(vertex=root_vertex)
distances: List[Optional[float]] = [
None for _ in range(graph.vertex_count)]
distances[first_idx] = 0
path_dict: Dict[int, Edge] = {}
priority_queue: PriorityQueue = PriorityQueue()
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=first_idx,
distance=0))
while not priority_queue.empty:
from_idx:int = priority_queue.pop().vertex_idx
from_vertex_distance: float = distances[from_idx]
for edge in graph.edges_at(vertex_index=from_idx):
#Already set to the target vertex before the target iteration
#Get the distance (value set by another route, etc.).
to_distance: Optional[float] = distances[edge.to_idx]
#Calculate the distance on this route.
current_route_distance: float = edge.weight + from_vertex_distance
#If the distance on another route has already been set, and on this route
#If the distance is not shorter, the update process is skipped.
if (to_distance is not None
and to_distance <= current_route_distance):
continue
distances[edge.to_idx] = current_route_distance
path_dict[edge.to_idx] = edge
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=edge.to_idx,
distance=current_route_distance))
return distances, path_dict
RoutePath = List[Edge]
def to_route_path_from_path_dict(
start_vertex_idx: int,
last_vertex_idx: int,
path_dict: Dict[int, Edge]) -> RoutePath:
"""
Using a dictionary that stores the edge just before the shortest distance to reach that path,
The shortest distance to the specified vertex
Parameters
----------
start_vertex_idx : int
The apex that is the starting point of the route you want to find
last_vertex_idx : int
The index of the vertices that are the final points of the route you want to find.
path_dict : dict
The key is the index of the target vertex, and the value is the shortest path to that vertex.
A dictionary containing the previous edge.
"""
route_path: RoutePath = []
current_edge: Edge = path_dict[last_vertex_idx]
route_path.append(current_edge)
while current_edge.from_idx != start_vertex_idx:
current_edge = path_dict[current_edge.from_idx]
route_path.append(current_edge)
route_path.reverse()
return route_path
if __name__ == '__main__':
graph = Graph(
vertices=[
Vertex.A,
Vertex.B,
Vertex.C,
Vertex.D,
Vertex.E,
Vertex.F,
Vertex.G,
Vertex.H,
Vertex.I,
Vertex.J,
Vertex.K,
])
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.B,
weight=80)
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.E,
weight=200)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.C,
weight=92)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.D,
weight=83)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.E,
weight=210)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.D,
weight=43)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.E,
weight=93)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.F,
weight=66)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.G,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.H,
weight=123)
graph.add_edge_by_vertices(
from_vertex=Vertex.E,
to_vertex=Vertex.F,
weight=81)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.G,
weight=46)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.K,
weight=100)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.H,
weight=141)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.I,
weight=53)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.K,
weight=112)
graph.add_edge_by_vertices(
from_vertex=Vertex.H,
to_vertex=Vertex.I,
weight=86)
graph.add_edge_by_vertices(
from_vertex=Vertex.I,
to_vertex=Vertex.J,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.J,
to_vertex=Vertex.K,
weight=92)
print('-' * 20)
print('Graph information:')
print(graph)
print('-' * 20)
distances, path_dict = dijkstra(
graph=graph,
root_vertex=Vertex.A)
print('Shortest distance information from the calculated vertex A to each vertex:')
for index, distance in enumerate(distances):
vertex: VertexStr = graph.vertex_at(index=index)
print('vertex:', vertex, 'distance:', distance)
print('-' * 20)
start_vertex_idx = graph.index_of(vertex=Vertex.A)
last_vertex_idx = graph.index_of(vertex=Vertex.J)
route_path: RoutePath = to_route_path_from_path_dict(
start_vertex_idx=start_vertex_idx,
last_vertex_idx=last_vertex_idx,
path_dict=path_dict)
print('Shortest path from vertex A to vertex J:')
for edge in route_path:
print(edge)
Reference site / reference summary
- Classic Computer Science Problems in Python -Dijkstra's algorithm (shortest path problem) -[Vertex (graph theory)-Wikipedia](https://ja.wikipedia.org/wiki/%E9%A0%82%E7%82%B9_(%E3%82%B0%E3%83%A9%E3) % 83% 95% E7% 90% 86% E8% AB% 96)) -Graph theory-Wikipedia -Graph theory
Recommended Posts