forked from OmkarPathak/pygorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdijkstra.py
More file actions
86 lines (69 loc) · 2.89 KB
/
dijkstra.py
File metadata and controls
86 lines (69 loc) · 2.89 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
"""
Dijkstra's Algorithm
Author: Timothy Moore
Dijkstra's algorithm is an algorithm for
finding the shortest paths between nodes
in a graph.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
"""
import heapq
import inspect
class Dijkstra(object):
"""Dijkstra object
Finds the optimal path between two nodes on
a graph.
"""
def __init__(self):
pass
@staticmethod
def reverse_path(node):
"""
Walks backward from an end node to the start
node and reconstructs a path. Meant for internal
use.
:param node: dict containing { 'vertex': any hashable, 'parent': dict or None }
:return: a list of vertices ending on the node
"""
result = []
while node is not None:
result.insert(0, node['vertex'])
node = node['parent']
return result
def find_path(self, graph, start, end):
"""
Calculates the optimal path from start to end
on the graph. Weights are ignored.
:param graph: object contains `graphs` as per pygorithm.data_structures.WeightedUndirectedGraph
weights are ignored.
:param start: the start vertex (which is the same type of the verticies in the graph)
:param end: the end vertex (which is the same type of the vertices in the graph)
:return: a list starting with `start` and ending with `end`, or None if no path is possible.
"""
_open = []
closed = set()
# the first element in the tuple is the distance from the source. This is used as the primary
# key for sorting. The second element in the tuple is just a counter and is used to avoid having
# to hash the dictionary when the distance from the source is not unique.
# performance might be improved by also searching the open list and avoiding adding those nodes
# but since this algorithm is typically for examples only performance improvements are not made
counter = 0
heapq.heappush(_open, (0, counter, {'vertex': start, 'parent': None}))
counter += 1
while len(_open) > 0:
current = heapq.heappop(_open)
current_dict = current[2]
closed.update(current_dict['vertex'])
if current_dict['vertex'] == end:
return self.reverse_path(current_dict)
neighbors = graph.graph[current_dict['vertex']]
for neighbor in neighbors:
if neighbor not in closed:
heapq.heappush(_open, (current[0] + 1, counter, {'vertex': neighbor, 'parent': current_dict}))
counter += 1
return None
@staticmethod
def get_code():
"""
returns the code for the current class
"""
return inspect.getsource(Dijkstra)