안녕하세요.다익스트라는 에지의 가중치가 양수일때 출발노드에서 전체 각 노드까지의 최단거리,벨만-포드는 특정 출발노드에서 다른 노드까지의 최단 경로 탐색, 음수 가중치가 있어도 수행 가능이렇게 되어있는데, 벨만-포드에서 에지 사용 횟수를 강조하는 이유가 다익스트라는 출발 노드가 정해져있고, 벨만-포드는주어진 출발노드가 달라질수 있어서라고 생각하면 될까요..?처음엔 가중치 양수, 음수만의 차이만 인줄 알았는데, 뭔가 강조하시는걸 보니 저런 이유때문인가하고 질문해봅니다..!다들 화이팅

def dijkstra(graph, start, final): # 각 노드들의 비용을 저장 costs = {} # 우선순위 큐 pq = [] # (해당위치까지 가는 총 비용, 노드위치) heapq.heappush(pq, (0, start)) while pq: # heappop을 하면 가장 작은 원소가 튀어 나온다. cur_cost, cur_v = heapq.heappop(pq) # 방문하지 않은 백터 일때만 작동 if cur_v not in costs: # costs[cur_v] = cur_cost for cost, next_v in graph[cur_v]: next_cost = cur_cost + cost heapq.heappush(pq, (next_cost, next_v)) return costs[final]해당 템플릿 코드중에서 if cur_v not in costs: costs[cur_v] = cur_cost어떻게 costs에 cur_v가 없다는 것 만으로 바로 최적의 경로라고 확신할 수 있는지 의문이 있습니다. heapq의 성질덕에 cur_cost, cur_v가 '지금까지 heap에 넣은 값들중에' 가장 작은 값 인거는 알겠는데 다른 경로를 통해 뒤늦게 heap에 들어간 값이 이전에 costs에 not in이여서 넣은 값보다 작은 경우도 있지 않나요??뭔가 제 생각에 자연스럽지 않아서 다른 코드들을 찾아보니 아래와 같이 제가 생각한 조건대로 대소 비교를 해보고 넣더군요.def dijkstra(graph,start,end): costs = {vertex:111111 for vertex in graph} pq = [] heapq.heappush(pq,(0,start)) while pq: cur_cost, cur_v = heapq.heappop(pq) if costs[cur_v] < cur_cost: continue for cost, next_v in graph[cur_v]: next_cost = cur_cost + cost if next_cost < costs[next_v]: costs[next_v] = next_cost heapq.heappush(pq, (next_cost, next_v)) return costs[end] " '지금까지 heap에 넣은 값들중에' 가장 작은 값 " 이 아니라 앞으로 나올 값 중에 가장 작은 근거가 있을까요??- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

import heapq def solution(N, road, K): n_road = [500001] * (N+1) n_road[1] = 0 sorted_road = [[] for i in range(N+1)] for road_num in road: sorted_road[road_num[0]].append([road_num[2], road_num[1]]) sorted_road[road_num[1]].append([road_num[2], road_num[0]]) # print(sorted_road) q = [] heapq.heappush(q, [0, 1]) while q: cur_node = q.pop() for dist, b in sorted_road[cur_node[1]]: if dist + n_road[cur_node[1]] < n_road[b]: # 1에서 cur로, cur에서 b로, 1에서 b로 n_road[b] = dist + n_road[cur_node[1]] q.append([n_road[b], b]) return len(list(filter(lambda x: x <=K, n_road))) 다익스트라 알고리즘을 구현하는데 의문점이 생겨서 여기 질문을 남깁니다. 1. 다익스트라 알고리즘에서 인접한 거리의 노드를 선택하기 위해서 heap 자료구조를 사용하는데 꼭 인접한 거리의 노드를 선택해야할 이유가 있을까요? 제가 원래 heap을 사용했던 python 코드를 단순히 배열로 바꿔서 가장 인접한 거리의 노드부터 선택하지 않음에도 불구하고 작동이 잘 되어서 질문을 남깁니다. - 제가 구현한 코드에서는 인접한 거리를 방문하든 안하든 결국 모든 노드들을 방문하여서 차이가 없다고 생각되었습니다. 2. 위와 같은 방법의 시간 복잡도는 어떻게 되는것인가요? 아직 시간복잡도 계산이 미숙해서 그런지 잘 모르겠습니다.