[trouble #2] dijkstra algorithm

kamchur·2022년 7월 25일
0

😁START

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]]]

other code : dijkstra algorithm

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


other code : improved dijkstra algorithm

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 :)


😂END

2022.07.25. first commit
2022.07.26. add other code dijkstra algorithm

example from '이것이 코딩테스트다'-나동빈(한빛미디어) p.239

profile
chase free

0개의 댓글