다익스트라 구현 카피코딩, 혼자해보기

다익스트라 알고리즘은 그리디 방식의 최단경로 알고리즘이다.

만든 사람 이름이 다익스트라라서 다익스트라 최단경로 알고리즘으로 불린다.

원리는 간단하다.

시작노드부터 해서 현재 방문할 수 있는 노드들 중 최단경로가 제일 짧은 노드들을 방문하면서 최단경로 테이블을 갱신하는 것이다. 

 

나동빈 저자분의 소스코드 : python-for-coding-test/2.py at master · ndb796/python-for-coding-test · GitHub

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

문제될까봐 코드를 여기다 그대로 쓰진 못하고 깃허브 링크를 걸어놓는다.

 

10분만 쉬었다가 입출력만 그대로 유지해놓고 다익스트라 알고리즘을 안보고 구현해봐야겠다.

 

import heapq
import sys

INF = 99999999

...(생략)....

########TODO : implement this function ##################
def dijkstra(start):
    pass

####################################################

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

 

10분이 지났고 혼자 구현해봤다.

import heapq
import sys

INF = 99999999

n, m = map(int,input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    # cost of node a -> node b is c 

########TODO : implement this function ############
def dijkstra(start):
    q = []

    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if dist > distance[now]:
            continue

        for node,cost in graph[now]:
            cost += dist
            if distance[node] > cost:
                distance[node] = cost
                heapq.heappush(q,(cost,node))

####################################################

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

저자님 코드를 본지 얼마 안되어서 그런지 저자님코드랑 거의 똑같은게 함정..ㅋㅋㅋ 기억의 영향을 좀 받아서;; 다음에 또 구현해봐야지