s434681/praca_magisterska
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
master
praca_magisterska/algorithms/dijkstra.py

65 lines
3.7 KiB
Python
Raw Permalink Normal View History

Changed binary heap to Fibonaccie's heap. Got rid of placeholder data.
2022-09-23 16:06:04 +02:00
import fibheap
Implemented dijkstra algorithm with priority queue in binary heap.
2021-10-17 11:21:09 +02:00
Rewrote all 3 algorithms. Generated 10 random graphs and grids for tests. Created testing structure which uses generated graphs and grids as input data to algorithms, measures execution time and memory blocks used by them. Takes these measurements and found weights and builds tables in latex format which compare these data among those three algorithms.
2022-09-25 16:41:41 +02:00
def dijkstra_algorithm(s, t, N, A, w):
"""
Implemented dijkstra algorithm with priority queue in binary heap.
2021-10-17 11:21:09 +02:00
Rewrote all 3 algorithms. Generated 10 random graphs and grids for tests. Created testing structure which uses generated graphs and grids as input data to algorithms, measures execution time and memory blocks used by them. Takes these measurements and found weights and builds tables in latex format which compare these data among those three algorithms.
2022-09-25 16:41:41 +02:00
:param graph:
:param start:
:param goal:
:param is_directed:
:return:
"""
if s == t:
return [s], 0
Implemented dijkstra algorithm with priority queue in binary heap.
2021-10-17 11:21:09 +02:00
Rewrote all 3 algorithms. Generated 10 random graphs and grids for tests. Created testing structure which uses generated graphs and grids as input data to algorithms, measures execution time and memory blocks used by them. Takes these measurements and found weights and builds tables in latex format which compare these data among those three algorithms.
2022-09-25 16:41:41 +02:00
H = fibheap.makefheap()
d = {}
heap_node_connection = {}
pred = {}
Implemented dijkstra algorithm with priority queue in binary heap.
2021-10-17 11:21:09 +02:00
Rewrote all 3 algorithms. Generated 10 random graphs and grids for tests. Created testing structure which uses generated graphs and grids as input data to algorithms, measures execution time and memory blocks used by them. Takes these measurements and found weights and builds tables in latex format which compare these data among those three algorithms.
2022-09-25 16:41:41 +02:00
for i in N:
d[i] = float('inf')
d[s] = 0
pred[s] = None
heap_node_connection[s] = fibheap.fheappush(H, 0, s)
success = False
while H.num_nodes > 0:
i = fibheap.fheappop(H)[1]
if i == t:
success = True
break
for j in A[i]:
path_sum = d[i] + w[(i, j)]
if d[j] > path_sum:
pred[j] = i
if d[j] == float('inf'):
d[j] = path_sum
heap_node_connection[j] = fibheap.fheappush(H, path_sum, j)
Changed implementation of Dijkstra algorithm a little.
2022-08-28 18:03:26 +02:00
else:
Rewrote all 3 algorithms. Generated 10 random graphs and grids for tests. Created testing structure which uses generated graphs and grids as input data to algorithms, measures execution time and memory blocks used by them. Takes these measurements and found weights and builds tables in latex format which compare these data among those three algorithms.
2022-09-25 16:41:41 +02:00
d[j] = path_sum
H.decrease_key(heap_node_connection[j], path_sum)
if success:
path = [t]
current_node = t
while pred[current_node] is not None:
path.append(pred[current_node])
current_node = pred[current_node]
path.reverse()
return path, d[t]
return None, None
Created two python packages. One for algorithms implementations of the master thesis and the other for methods, classes and structures meant to help with the use of those algorithms.
2021-10-08 18:16:04 +02:00
if __name__ == "__main__":
Rewrote all 3 algorithms. Generated 10 random graphs and grids for tests. Created testing structure which uses generated graphs and grids as input data to algorithms, measures execution time and memory blocks used by them. Takes these measurements and found weights and builds tables in latex format which compare these data among those three algorithms.
2022-09-25 16:41:41 +02:00
N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A = {1: [2, 8, 6], 2: [1, 3, 5], 8: [1, 4], 3: [2], 5: [2, 7, 9, 10], 4: [6, 7, 8], 6: [4, 1], 7: [4, 5], 9: [5], 10: [5]}
A_b = {2: [1, 3, 5], 1: [2, 8, 6], 8: [1, 4], 3: [2], 5: [2, 7, 9, 10], 6: [4, 1], 4: [6, 7, 8], 7: [4, 5], 9: [5], 10: [5]}
w = {(1, 2): 84, (2, 1): 84, (1, 8): 52, (8, 1): 52, (2, 3): 4, (3, 2): 4, (2, 5): 39, (5, 2): 39, (4, 6): 74, (6, 4): 74, (4, 7): 81, (7, 4): 81, (5, 7): 45, (7, 5): 45, (5, 9): 66, (9, 5): 66, (5, 10): 19, (10, 5): 19, (4, 8): 87, (8, 4): 87, (1, 6): 4, (6, 1): 4}
print(dijkstra_algorithm(1, 10, N, A, w))
Implemented dijkstra algorithm with priority queue in binary heap.
2021-10-17 11:21:09 +02:00
Rewrote all 3 algorithms. Generated 10 random graphs and grids for tests. Created testing structure which uses generated graphs and grids as input data to algorithms, measures execution time and memory blocks used by them. Takes these measurements and found weights and builds tables in latex format which compare these data among those three algorithms.
2022-09-25 16:41:41 +02:00
N = {(3, 4), (5, 7), (7, 7), (6, 5), (4, 5), (3, 3), (4, 8), (3, 6), (8, 5), (6, 4), (6, 7), (3, 5), (5, 5), (5, 8), (8, 7), (2, 6), (6, 6), (7, 5), (7, 8)}
A = {(2, 6): [(3, 6)], (3, 3): [(3, 4)], (3, 4): [(3, 3), (3, 5)], (3, 5): [(4, 5), (3, 4), (3, 6)], (3, 6): [(2, 6), (3, 5)], (4, 5): [(3, 5), (5, 5)], (4, 8): [(5, 8)], (5, 5): [(4, 5), (6, 5)], (5, 7): [(6, 7), (5, 8)], (5, 8): [(4, 8), (5, 7)], (6, 4): [(6, 5)], (6, 5): [(5, 5), (7, 5), (6, 4), (6, 6)], (6, 6): [(6, 5), (6, 7)], (6, 7): [(5, 7), (7, 7), (6, 6)], (7, 5): [(6, 5), (8, 5)], (7, 7): [(6, 7), (8, 7), (7, 8)], (7, 8): [(7, 7)], (8, 5): [(7, 5)], (8, 7): [(7, 7)]}
A_b = {(3, 6): [(2, 6), (3, 5)], (3, 4): [(3, 3), (3, 5)], (3, 3): [(3, 4)], (3, 5): [(3, 4), (3, 6), (4, 5)], (4, 5): [(3, 5), (5, 5)], (2, 6): [(3, 6)], (5, 5): [(4, 5), (6, 5)], (5, 8): [(4, 8), (5, 7)], (6, 5): [(5, 5), (6, 4), (6, 6), (7, 5)], (6, 7): [(5, 7), (6, 6), (7, 7)], (4, 8): [(5, 8)], (5, 7): [(5, 8), (6, 7)], (7, 5): [(6, 5), (8, 5)], (6, 4): [(6, 5)], (6, 6): [(6, 5), (6, 7)], (7, 7): [(6, 7), (7, 8), (8, 7)], (8, 5): [(7, 5)], (8, 7): [(7, 7)], (7, 8): [(7, 7)]}
w = {((2, 6), (3, 6)): 1, ((3, 3), (3, 4)): 1, ((3, 4), (3, 3)): 1, ((3, 4), (3, 5)): 1, ((3, 5), (4, 5)): 1, ((3, 5), (3, 4)): 1, ((3, 5), (3, 6)): 1, ((3, 6), (2, 6)): 1, ((3, 6), (3, 5)): 1, ((4, 5), (3, 5)): 1, ((4, 5), (5, 5)): 1, ((4, 8), (5, 8)): 1, ((5, 5), (4, 5)): 1, ((5, 5), (6, 5)): 1, ((5, 7), (6, 7)): 1, ((5, 7), (5, 8)): 1, ((5, 8), (4, 8)): 1, ((5, 8), (5, 7)): 1, ((6, 4), (6, 5)): 1, ((6, 5), (5, 5)): 1, ((6, 5), (7, 5)): 1, ((6, 5), (6, 4)): 1, ((6, 5), (6, 6)): 1, ((6, 6), (6, 5)): 1, ((6, 6), (6, 7)): 1, ((6, 7), (5, 7)): 1, ((6, 7), (7, 7)): 1, ((6, 7), (6, 6)): 1, ((7, 5), (6, 5)): 1, ((7, 5), (8, 5)): 1, ((7, 7), (6, 7)): 1, ((7, 7), (8, 7)): 1, ((7, 7), (7, 8)): 1, ((7, 8), (7, 7)): 1, ((8, 5), (7, 5)): 1, ((8, 7), (7, 7)): 1}
print(dijkstra_algorithm((3, 3), (4, 8), N, A, w))
Reference in New Issue Copy Permalink