[leetcode 743] Network Delay Time

심지훈·2021년 6월 13일
0

leetcode

목록 보기
12/21

리트코드 문제

이 문제는 문제 풀이에 대한 반추보다는 다익스트라 알고리즘에 대한 반추를 하려고 한다.

다익스트라 알고리즘은 그래프에서 시작점을 기준으로 최단거리를 찾는 알고리즘이다. 그래프의 가중치에 음수가 있으면 안된다.

다익스트라 알고리즘은 시작점에 연결되어있는 노드들을 먼저 우선순위 큐에 넣고 알고리즘을 시작한다. 우선순위의 기준은 u라는 노드에서 v 노드까지 갈때의 거리 w가 낮은 순이다.

그다음에는 인접한 노드들 중 우선순위, 즉 가중치가 낮은 노드들을 먼저 연결해나가다가 이미 방문한 노드의 가중치가 새로 계산한 노드의 가중치보다 높다면 노드의 가중치를 업데이트 한다. 그리고 해당 인접노드를 우선순위 큐에 넣고 노드를 다시 업데이트 해나간다.

def dijkstra(start):

    from collections import defaultdict
    import heapq

    graph = defaultdict(list)
    distance = [float('inf')] * number_of_nodes

    for information in graph_information:
        graph.append((next_node, w))

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

    while q:

        w, u = heapq.heappop(q)

        if distance[u] < w:
            continue

        for next_node, cost in graph[u]:
            dist = cost + w
            if dist < distance[next_node]:
                distance[next_node] = dist
                heapq.heappush(q,(dist,next_node))

힙에 넣고 각 노드를 탐색하며 노드에 닿는 비용이 새로 계산 된 값보다 더 크다면 비용을 갱신하는 형식의 방법이다.

        for next_node, cost in graph[u]:
            dist = cost + w
            if dist < distance[next_node]:
                distance[next_node] = dist

힙의 특성을 이용 이 보다 조금 더 간단하게 알고리즘을 구현 할 수 있다.

while q:
            
	time, node = heapq.heappop(q)
	if node not in dist:
		dist[node] = time
                
		for v,w in graph[node]:
			heapq.heappush(q,(time+w, v))

힙에 의해 임의의 노드 a로 가는 경로의 가중치는 항상 작은 값부터 들어가기 때문에 딕셔너리 dist에 그 값이 없다면 가중치를 갱신하면 되고 이미 있다면, 현재의 가중치보다 더 낮은 가중치가 이전에 나와서 가중치를 갱신했다는 것이고. 힙에 의해 먼저 나온 가중치가 나중에 나온 가중치보다 작으므로 위와같이 하더라도 최솟값을 보장한다.

profile
유연한 개발자

0개의 댓글