최단 경로와 그리디 다익스트라 알고리즘

다익스트라 알고리즘 : 탐욕법

 - 단일 정점에서 모든 다른 정점으로의 최단 경로 구하기

 - 최소비용 신장트리 mst의 프림 알고리즘과 유사

 - 차이점은 프림 알고리즘은 V-Y집합과 인접한 노드를 넣어준다면 다익스트라는 출발점 v1과 가장 Y의집합을 touch하고

 가장 인접한 노드를 넣어준다.

 

종료 조건문은 if Y == V: 같으면 탐색을 완료했다고 표현

 

 옆에 그림의 경로는 F = {}

v1 -> v5 , 1

(v1->)v5 -> v4 , 2

v1 -> v3, 4

(v1->v5->)v4 -> v2, 5

정보가 저장된다.

 

 

 

 

 

표를 보면 알 수 있듯이

v1 -> v5로의 경로가 입력되면서

5번은 -1로 방문체크가 완료되며

v1 -> v4로 갈수있는 비용이 6 -> 2로 바뀌게 된다

이건 v1->v5->v4로 갈수있는 비용 2가 업데이트 된 것이다

distance[vnear] + w[vnear][i]

 

출처 : https://www.youtube.com/watch?v=yhwOQflQehk 

 

 

inf = 999
w = [
    [-1,-1,-1,-1,-1,-1],
    [-1,0,7,4,6,1],
    [-1,inf,0,inf,inf,inf],
    [-1,inf,2,0,5,inf],
    [-1,inf,3,inf,0,inf],
    [-1,inf,inf,inf,1,0]
]

def dijkstra(w):
    n = len(w)-1
    F = []
    touch = [-1] * (n+1)
    distance = [-1] * (n+1)
    for i in range(2,n+1):
        touch[i] = 1
        distance[i] = w[1][i]

    for _ in range(n-1):
        minvalue = inf
        for i in range(2,n+1):
            if 0<=distance[i]<minvalue:
                minvalue = distance[i]
                vnear = i
        edge = (touch[vnear], vnear, w[touch[vnear]][vnear])
        F.append(edge)
        for i in range(2,n+1):
            if distance[i] > distance[vnear] + w[vnear][i]:
                distance[i] = distance[vnear] + w[vnear][i]
                touch[i] = vnear
        distance[vnear] = -1

    return F


print(dijkstra(w))

 

 

## 우선순위 queue로 구현한 다익스트라

import sys
import heapq
sys.stdin = open('inputs.text')
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

vertex_num,e = map(int,sys.stdin.readline().split())
start = int(sys.stdin.readline())
graph = [[] for i in range(vertex_num+1)]
for _ in range(e):
  u,v,w = map(int,sys.stdin.readline().split())
  graph[u].append([v,w])


def djikstra(start,w):

  distance = [INF] * (vertex_num+1)
  distance[start] = 0
  queue = []
  heapq.heappush(queue,[w,start])

  while queue:
    cost, now_node = heapq.heappop(queue)
    if distance[now_node] < cost:
      continue
    for next_node,cst in graph[now_node]:
      spanning = cost + cst
      if distance[next_node] > spanning:
        distance[next_node] = spanning
        heapq.heappush(queue,[spanning,next_node])

  for x in distance[1:]:
    if x == INF:
      print('INF')
    else:
      print(x)
  return

djikstra(start,0)