다익스트라python

다익스트라 알고리즘(python기준)

• 매일 구현하려고 하면 까먹어서 저장용
• 참고

코드

import queue # 우선순위 큐 용
INF = int(1e9) # 최대치는 그때마다 수정하면됨
def dijkstra(src,dst,adj):
    q = queue.PriorityQueue() # 거리, 위치
    
    n = len(adj) 
    # 거리저장
    dist = [INF for _ in range(n)]
    # 처음위치 초기화
    dist[src] = 0
    q.put((0,src)) # 우선순위로 시작
    while q.qsize()>0:
        l,s = q.get() 
        if l > dist[s]: # 저장된위치dist[x]가 이미 최소로 되어있음
            continue
        
        for a in adj[s]:  # s에서 시작해서 연결된 경로들 확인
            # a는 [도착,거리요금]
            d = a[0]
            cost = a[1]+l # s->d거리 + l(src에서 s까지의 거리)
            #dist[d] vs cost
            if cost < dist[d]:
                dist[d] = cost
                q.put((cost,d))
    return dist[dst]

# 인접리스트를 만들기
def mkAdjList(n,fares):
    adj = [[] for _ in range(n)]
    for f in fares:
        adj[f[0]-1].append([f[1]-1,f[2]]) # 노드가 1부터 시작하면 -1해줘서 좀더 편하게 계산하자
        adj[f[1]-1].append([f[0]-1,f[2]])
    return adj