I also implemented Dijkstra's algorithm in python to study Dijkstra's algorithm. As an example, I used "D-Treasure Hunt of AtCoder Beginner Contest 035" that first appeared in "Dijkstra AtCoder".
I don't understand the difference between Dijkstra's algorithm, DFS, and BFS, so I will briefly summarize the results of my research. (DFS and BFS are implemented below) Implement depth-first search (DFS) and breadth-first search (BFS) in python
--DFS (depth-first search) / BFS (breadth-first search) --Algorithms for searching for unweighted graphs --Dijkstra's algorithm --Algorithm for searching for breadth-first graphs (an extended version of BFS because it uses queues (more precisely, weighted queues))
Dijkstra's Algorithm
start → The shortest route to reach the destination is g_list, go
Manage the shortest route from destination to start with b_list, back
#ABC035 D Treasure Hunt
import heapq
def dijkstra(s, n, c_list):
_list = [float("Inf")]*n
_list[s] = 0
hq = [[0,s]]
heapq.heapify(hq)
while len(hq) > 0:
_ci, _i = heapq.heappop(hq)
if _list[_i] < _ci:
continue
for _cj,_j in c_list[_i]:
if _list[_j] > (_list[_i] + _cj):
_list[_j] = _list[_i] + _cj
heapq.heappush(hq, [_list[_j],_j])
return _list
n, m, t = map(int, input().split())
a_list = [int(x) for x in input().split()]
g_list = [[] for i in range(n)]
b_list = [[] for i in range(n)]
for i in range(m):
_a, _b, _c = map(int, input().split())
g_list[_a-1].append([_c,_b-1])
b_list[_b-1].append([_c,_a-1])
go = dijkstra(0, n, g_list)
back = dijkstra(0, n, b_list)
ans = 0
for i in range(n):
_tmp = t - (go[i] + back[i])
if a_list[i]*_tmp > ans:
ans = a_list[i]*_tmp
print(ans)
Recommended Posts