# 최단경로 # 그래프 초기화 graph = 그래프 생성() graph.add_edges([(벌, 꽃A), (꽃A, 꽃B), ..., (꽃n, 벌통)]) # 간선 생성 graph.es["거리"] = [d1, d2, ...] # 거리 가중치 순서대로 설정 # 상태 초기화 dist = {벌: 0, 꽃A: ∞, 꽃B: ∞, ..., 벌통: ∞} # 시작 노드(벌)에서 해당 노드까지의 최단 거리 # 시작 노드는 0, 나머지는 무한대 prev = {벌: None, 꽃A: None, ..., 벌통: None} # 최단 경로 역추적용 # 더 짧은 경로 발견 시 갱신 우선순위 큐 = [(0, 벌)] # (거리, 노드) 형태로 저장, 거리=시작노드부터의 누적거리 # 다음 탐색 노드의 거리와 노드 저장, 꺼낼 때 거리 짧은 순으로 나옴 # 다익스트라 이동 while 우선순위 큐가 비어있지 않다: # 탐색할 후보가 남아있는 동안 반복 현재 거리, 현재 노드 = 우선순위 큐에서 거리가 가장 짧은 노드 꺼내기 # 큐에서 (거리, 노드) 꺼내서 저장 if 현재 노드 == 벌통: # 벌통 도착 시 종료 break elif 현재 거리 > dist[현재 노드]: # 이미 더 짧은 경로로 방문했으면 스킵 continue else: # 현재 노드의 거리가 저장된 거리보다 짧거나 같은 경우만 탐색을 진행 이동 가능한 노드 = [현재 노드와 연결된 노드 목록] # 현재 노드의 주변 노드 탐색 for 다음 노드 in 이동 가능한 노드: 새 거리 = 현재 거리 + (현재 노드와 다음 노드 사이의 거리) if 새 거리 < dist[다음 노드]: # 현재 노드에 인접한 노드들이 저장된 거리보다 짧을 경우만 갱신 dist[다음 노드] = 새 거리 # 거리 갱신 prev[다음 노드] = 현재 노드 # 경로 갱신 우선순위 큐에 (새 거리, 다음 노드) 추가 # 발견한 주변 노드를 우선순위 큐에 넣음 # 최단 경로 역추적 방문 경로 = [] 현재 노드 = 벌통 while 현재 노드 != None: 방문 경로 앞에 현재 노드 추가 현재 노드 = prev[현재 노드] # 결과: 방문 경로 = [벌, 꽃A, 꽃C, 벌통] 처럼 최단 경로가 완성됨 # 결과 출력 print(총 이동 거리: dist[벌통], 방문 경로)
Euisaac Toast