최단경로알고리즘-[다익스트라-Dijkstra's Algorithm)

- 하나의 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘(간선의 가중치가 양수일 때만)

 

https://people.ok.ubc.ca/ylucet/DS/Dijkstra.html

Dijkstra Visualization

 

 

다익스트라 시각화

a와 b 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다.

탐색 알고리즘

그래프

시간복잡도 O(|E|+|V|log|V|)}

출처 : 위키백과

#코드

import sys
# T[i] : 정점 i에 도달하는데 걸리는 최단거리
# for i = 0 ~ n 
# (1) T[i] 중 최솟값을 정한다. 단, 지금까지 최솟값으로 뽑히지 않았던 값들 중.
# (2) 최솟값을 가진 노드의 idx로부터 뻗어나간다. T[idx] + cost 
 
if __name__ == "__main__": 
   
  n, m, start, end = map(int, sys.stdin.readline().split()) 
  myGraph = [[] for i in range(n+1)]
  cost    = [[] for i in range(n+1)]
  
  table   = [0]*(n+1)
  # check[i] = True : 이미 i는 최단거리가 확정되었다.
  # check[i] = False : 이미 i는 최단거리가 확정되지 않았다.
  check   = [0]*(n+1)
  
  for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    # a -- (c) -- b
    
    myGraph[a].append(b)
    myGraph[b].append(a)
    
    cost[a].append(c)
    cost[b].append(c)
    
  
  for i in range(n):
    table[i] = 987987987
  table[start] = 0
  
  for i in range(n):
    # (1) 최솟값을 구한다. 단, 지금까지 최단거리로 확정되지 않았던 정점에 대해서.
    # (2) 그 최솟값을 갖는 노드로부터 뻗어나간다.
    minValue, minIdx = 987987897, -1
    for j in range(n):
      if check[j] == False and minValue > table[j]:
        minValue = table[j]
        minIdx = j
      
    check[minIdx] = True
    for j in range(len(myGraph[minIdx])):
      node2 = myGraph[minIdx][j]
      cost2 = cost[minIdx][j]
      
      # minIdx -- (cost2) -- node2
      if table[node2] > table[minIdx] + cost2:
        table[node2] = table[minIdx] + cost2
      
    
 #print(myGraph)
 #print(cost)
  print(table[end])
   
'''
# 입력 값 정보
# 8 정점의 정보 11 간선의 정보 0 시작 6 도착
# 0 에서 1 까지 이어져 있다. 3 가중치
8 11 0 6 
0 1 3
0 5 1
1 2 4
1 3 1
1 5 1
2 4 6
2 6 9
2 7 4
3 4 2
4 6 9
6 7 3
'''

입력
8 11 0 6 
0 1 3
0 5 1
1 2 4
1 3 1
1 5 1
2 4 6
2 6 9
2 7 4
3 4 2
4 6 9
6 7 3

출력
13

 

# 복습

import sys
 
# T[i] : 정점 i에 도달하는데 걸리는 최단거리
# for i = 0 ~ n
 
# (1) T[i] 중 최솟값을 정한다. 단, 지금까지 최솟값으로 뽑히지 않았던 갑들 중.
# (2) index로부터 뻗어나간다. T[index] + cost
 
if __name__ == "__main__":
  input = sys.stdin.readline
  n, m, start, end = map(int, input().split())
  myGraph      = [[] for _ in range(n)]
  cost         = [[] for _ in range(n)]
  table        = [int(1e9)] * n
  table[start] = 0
  check        = [False] * n # check[i] = True : 이미 i는 최단거리가 확정되었다.
  
  for _ in range(m):
    a, b, c = map(int, input().split())
    # 그래프
    myGraph[a].append(b)
    myGraph[b].append(a)
    # 가중치
    cost[a].append(c)
    cost[b].append(c)
  
  # 다익스트라 알고리즘 
  for _ in range(n): # 모든 정점의 최단거리를 알아야하므로 정점의 개수만큼 돌아준다.
  
    # (1) 최솟값을 구한다. 단, 지금까지 최단거리로 확정되지 않았던 정점에 대해서
    print(table)
    min_value = int(1e9)
    min_index = -1
    for j in range(n):
      if not check[j] and min_value > table[j]:
        min_value = table[j]
        min_index = j
        
    check[min_index] = True
    
    # (2) 그 최솟값을 갖는 노드로부터 뻗어나간다.
    for j in range(len(myGraph[min_index])):
      # min_index ---(cost2)--- node2
      node2 = myGraph[min_index][j]
      cost2 = cost[min_index][j]
      # 해당 위치가 최단거리인지 
      if table[node2] > table[min_index] + cost2:
        table[node2] = table[min_index] + cost2
  
  print(myGraph)
  print(cost)
  print(table[end])
  
  
 
'''
8, 11 : 정점 개수, 간선 개수
0, 6  : 시작점과 끝점
 
8 11 0 6
0 1 3
0 5 1
1 2 4
1 3 1
1 5 1
2 4 6
2 6 9
2 7 4
3 4 2
4 6 9
6 7 3
 
'''

 

 

시간 복잡도

하나는 각 정점마다 인접한 간선들을 모두 검사하는 작업이고, 다른 하나는 우선순위 큐에 원소를 넣고 삭제하는 작업입니다. 각 정점은 정확히 한 번씩 방문되고, 따라서 모든 간선은 한 번씩 검사된다는 사실을 떠올리면 간선들을 검사하는 데는 전체 O(|E|)의 시간이 걸립니다.
우선순위 큐가 가장 커지는 최악의 시나리오는 그래프의 모든 간선이 검사될 때마다 dist[]가 갱신되고 우선순위 큐에 정점의 번호가 추가되는 것입니다. 이때 추가는 각 간선마다 최대 한 번 일어나기 때문에, 우선순위 큐에 추가되는 원소의 수는 최대 O(|E|)의 시간이 걸리고, O(|E|)개의 원소에 대해 이 작업을 하려면 전체 시간 복잡도는 O(|E||log|E|)가 됨을 알 수 있습니다.
이 두 작업에 걸리는 시간을 더하면 O(|E||log|E|)가 됩니다만, 대개의 경우 그래프에서 간선의 개수 |E|는 |V|^2보다 작기 때문에 O(log|E|)=O(log|V|)라고 볼 수 있습니다. 따라서 시간 복잡도는 O(|E||log|V|)가 됩니다.

 

시간복잡도 출처 : https://sungjk.github.io/2016/05/13/Dijkstra.html

다익스트라 알고리즘(Dijkstra)