가중치가 음수인 경우에 최단거리를 구하는 벨만 포드 알고리즘 익히기

1. 가중치에 음수가 포함된 경우 모든 간선의 비용이 양수일때는 다익스트라 알고리즘을 사용하면 특정 노드에서 다른 노드까지 최단 거리로 가는 비용을 효과적으로 구해준다 다음에서 1번 노드에서 다른 노드까지 가는 최단 비용은 얼마일까? 다익스트라 알고리즘을 이용해서 구하면 최단거리를 간단히 구할 수 있다 import heapq INF = 10000000000000000000000 dist = [INF]*7 graph = [[],[(2,6),(3,2)],[(3,2),(4,2)],[(5,1)],[(6,2)],[(2,1),(4,3),(6,4)],[]] q = [] heapq.heappush(q,(0,1)) dist[1] = 0 while q: d,u = heapq.heappop(q) if dist[u] < d:..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 12. 1.
• textsms

다익스트라 알고리즘에서 실제 최단 경로 구하기

1. 실제 최단 경로 역추적 지금까지 다익스트라 알고리즘에선 최단 경로로 가는데 걸리는 가중치의 합을 구해왔는데, 실제 최단 경로가 궁금할 수도 있다 어떻게 하면 구할 수 있을까? 결론부터 말하자면 경로를 역추적해서 구한다 어떤 정점 A에서 목적지 B로 가는데, "A,C,D,E,F,G,B로 가는게 최단 경로다" 이렇게 순방향으로 구하지 않고, 다익스트라 알고리즘에서 테이블에서 최단 거리를 가진 정점 u를 선택할때, u와 인접한 정점 b를 선택하는데, b의 거리가 테이블에서 갱신될때 "b와 가장 가까운 정점이 u이다"라고 테이블에 저장을 해놓는다 모든 과정이 종료되면 목적지 B와 가장 가까운 정점이 G이고, G와 가장 가까운 정점이 F이고 F와 가장 가까운 정점이 E이고, ... C와 가장 가까운 정점이 ..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 10. 10.
• textsms

최단 거리를 구하는 2번째 알고리즘 플로이드 워셜 알고리즘 파헤치기

1. 개요 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우"에 사용할 수 있는 알고리즘이다. -------------------------------------------------------------------------------------------------------- 다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하면서 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘은 또한 단계마다 "거쳐 가는 노드"를 기준으로 ..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 10. 9.
• textsms

2차원 배열에도 사용가능한 다익스트라 알고리즘

1. 문제 1249. [S/W 문제해결 응용] 4일차 - 보급로 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2차원 배열에서 (0,0)에서 (n-1,n-1)로 가는데, 경로에 쓰이는 숫자들의 합이 최소가 되도록 갈때, 그 최솟값을 구하는 문제 2. 풀이 2차원 배열에서도 다익스트라 알고리즘을 사용할 수 있을까? 그대로 사용하면 된다 2차원 배열을 하나의 그래프로 바꿀려고 시도한 적이 있었는데 그럴 필요도 없다 다익스트라 알고리즘이 distance 배열을 무한으로 초기화하고, 출발 위치는 0으로 시작한 다음에 현재 위치에서 인접한 곳으로 이동을 해보고, 거리가 최소가 되면 di..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 10. 7.
• textsms

특정한 정점을 반드시 거쳐야하는 최단 경로를 구하는 다익스트라 응용

1. 문제 1504번: 특정한 최단 경로 (acmicpc.net) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1번부터 n번까지 최단 경로로 이동하고 싶은데, 특정한 정점 v1,v2를 반드시 거쳐서 최단 경로로 가고 싶다면 어떻게 해야할까? 2. 풀이 다익스트라는 어떤 정점에서 나머지 정점까지 도달하는 최단 경로를 제공하는데, 여기 중간에 어떤 정점을 거칠지는 말해주지 않는다... 근데 어떤 정점을 반드시 거쳐가게 할려면 어떻게 해야할까? 생각보다 간단하다 1번..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 10. 6.
• textsms

자다가도 일어나서 바로 구현할 수 있어야하는 최단경로를 찾는 다익스트라 알고리즘 최적화하기 2편

1. 개요 다익스트라 알고리즘을 간단히 구현하면 시간 복잡도가 $O(V^{2})$이지만 이제부터 배울 구현 방법을 이용하면 최악의 경우에도 $O(ElogV)$를 보장하여 해결할 수 있다. 여기서 V는 노드의 개수이고 E는 간선의 개수이다. 간단한 다익스트라 알고리즘은 "최단 거리가 가장 짧은 노드"를 찾기 위해 매번 최단 거리 테이블을 선형적으로 (모든 원소를 앞에서부터 하나씩) 탐색해야 했다. 이 과정에서만 O(V)의 시간이 걸린다. 하지만 최단 거리가 가장 짧은 노드를 단순히 선형적으로 찾는 것이 아니라 더욱 더 빠르게 찾을 수 있다면 어떨까? 개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다. 힙 자료구조를 이용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하므로, 출발 노드부터..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2022. 10. 3.
• textsms