I don't understand dijkstra, floydwarsher, know shortest distance.
so I coding dijkstra example by self.
but which doubtful because my code very simple line.
my code
0 n, m = 6, 11
1 INF = 1e9
2
3 graph = [
4 [1, 2, 2],
5 [1, 3, 5],
6 [1, 4, 1],
7 [2, 3, 3],
8 [2, 4, 2],
9 [3, 2, 3],
10 [4, 3, 3],
11 [4, 5, 1],
12 [5, 3, 1],
13 [5, 6, 2],
14 ]
15
16 # 각 노드까지의 최단거리 구하시오.
17 # 부여 받은 노드의 수는 '6'개이다
18
19 # info객체 index는 해당 노드번호, 내부의 idx[0] = distance, idx[1] = path로 활용
20 # [[distance1,[path1]], [distance2, [path2]], [distance3, [path3]]]
21 info = [[INF, []] for _ in range(n)]
22 # info = [[INF, []]] * n 깊은 복사가 생겨서 데이터 갱신이 정상적으로 이루어지지 않음
23
24 info[0][0] = 0
25
26 for i in graph:
27 start = i[0]-1
28 end = i[1]-1
29 distance = i[2] + info[start][0]
30 path = info[start][1] + [i[0]]
31
32 if distance < info[end][0]:
33 info[end][0] = distance
34 info[end][1] = path
35
36 print(info)
22 line is deep copy(call by object referece)
if you use 22 line method, after someone replace elements, then the list elements replace all
so use 21 line method, recommend list comprehension.
27 line, start = start point(start node)
28 line, end = end point(target node)
29 line, return start ~ end distance
30 line, start ~ end path node list
32 line, compare origin distance and new distance, if end point node distance change more than minimum.
update distance and path
result.
[[0, []], [2, [1]], [3, [1, 4, 5]], [1, [1]], [2, [1, 4]], [4, [1, 4, 5]]]
0 n, m = 6, 11
1 INF = int(1e9)
2
3 graph = [[] for i in range(n+1)]
4
5 start = 1
6 visited = [False] * (n+1)
7 distance = [INF] * (n+1)
8
9 for _ in range(m):
10 a, b, c = map(int, input().split())
11 graph[a].append(b, c)
12
13
14 def get_smallest_node():
15 min_value = INF
16 index = 0
17 for i in range(1, n+1):
18 if distance[i] < min_value and not visited[i]:
19 min_value = distance[i]
20 index = i
21
22 return index
23
24
25 def dijkstra(start):
26 distance[start] = 0
27 visited[start] = True
28
29 for j in graph[start]:
30 distance[j[0]] = j[1] # j[0] = target node, j[1] = distance
31
32 for i in range(n-1):
33 now = get_smallest_node()
34 visited[now] = True
35
36 for j in graph[now]:
37 cost = distance[now] + j[1]
38
39 if cost < distance[j[0]]:
40 distance[j[0]] = cost
41
42
43 dijkstra(start)
44
45 for i in range(1, n+1):
46 if distance[i] == INF:
47 print("INFINITY")
48 else:
49 print(distance[i])
14 line, get_smallest_node()
check minimum distance to node
32 line, n-1
cause first start node check complete
39 line, compare new cost and exist distance size
use heap, heap library is have kind of two.
one is PriorityQueue library, two is heapq library.
the speed is faster heapq library more than PriorityQueue library.
0 import heapq
1
2 n, m = 6, 11
3 INF = int(1e9)
4
5 graph = [[] for i in range(n+1)]
6
7 start = 1
8 visited = [False] * (n+1)
9 distance = [INF] * (n+1)
10
11 for _ in range(m):
12 a, b, c = map(int, input().split())
13 graph[a].append(b, c)
14
15
16 def dijkstra(start):
17 q = []
18 heapq.heappush(q, (0, start))
19 distance[start] = 0
20
21 while q: # 큐가 비어있지 않으면 True
22 dist, now = heapq.heappop(q)
23
24 if distance[now] < dist:
25 continue
26
27 for i in graph[now]:
28 cost = dist + i[1]
29
30 if cost < distance[i[0]]:
31 distance[i[0]] = cost
32 heapq.heappush(q, (cost, i[0]))
33
34
35 dijkstra(start)
36
37 for i in range(1, n+1):
38 if distance[i] == INF:
39 print("INFINITY")
40 else:
41 print(distance[i])
18 line, heappush(value, material) priority (default=minimum)
22 line, heappop(queue) pop first element value
this code isn't search smallest_index before other code
queue heappop method makes it simple :)
2022.07.25. first commit
2022.07.26. add other code dijkstra algorithm
example from '이것이 코딩테스트다'-나동빈(한빛미디어) p.239