🗒️ shortest path (4)

1. 2021.07.22 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

   플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 모든 쌍 최단 경로(All-Pairs Shortest Path)를 구하는 알고리즘 O(V³)의 시간 복잡도와 O(V²)의 메모리 사용량으로 동작하는 상향식 알고리즘 벨만-포드 알고리즘 그래프의 두 정점 사이의 최단 경로가 출발 정점에서 시작하는 다른 최단 경로와 최종 목표 정점으로 연결된 에지의 조합으로 구성됨. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 은 이러한 개념에 좀 더 광범위한 일반화를 적용함으로써 큰 효과를 얻음. 정점 A와 정점 B 사이의 최단 거리가 AB이고, 정점 B와 정점 C 사이의 최단 거리가 BC이면, 정점 A와 정점 C 사이의 최단 거리는 AB + BC 임. 이 논리는 그 자체로 획기..
2. 2021.07.04 존슨 알고리즘(Johnson's Algorithm)

   존슨 알고리즘(Johnson's Algorithm) 벨만-포드 알고리즘 과 다익스트라 알고리즘 의 방법을 결합하여 모든 정점 사이의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘의 효율성을 활용함과 동시에 음수 가중치를 갖는 그래프에 대해서도 올바른 결과를 생성할 수 있음. 상당히 새로운 접근 방법을 사용함. 음수 가중치에 대한 다익스트라 알고리즘의 한계를 극복하기 위해 전체 에지 가중치를 음수가 아닌 형태로 변환 함. 벨만-포드 알고리즘 과 적절한 수학 논리 를 결합하여 이루어짐. 동작 방식 그래프에 새로운 더미(Dummy) 정점 을 추가함. 그리고 이 더미 정점과 나머지 모든 정점 사이에 가중치가 0인 에지를 연결함. 이후 벨만-포드 알고리즘 을 이용하여 더미 정점과 나머지 정점들 사이의 최단 경로..
3. 2021.06.30 다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm)

   다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm) 그래프에서 단일 시작(Single Start) 최단 경로 문제(Shortest Path Problem) 구글 지도 또는 자동차 내비게이션 등에서 경로를 탐색할 때 사용됨. 문제 정의 주어진 그래프 G = 의 시작 정점(Source Vertex) 과 목적 정점(Destination Vertex) 이 주어질 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하시오. V : 정점의 집합 E : 에지의 집합 각각의 에지는 가중치를 가지고 있음. 다익스트라 알고리즘(Dijkstra's Algorithm) 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘 프림의 MST 알고리즘을 약간 변경한 형태 ..
4. 2020.12.28 [Project Euler #15][C++] 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

   문제15 : 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수 문제 아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다). 그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까? 문제 해결 방법 격자에서 최단 경로의 수 를 찾는 문제이다.규칙성을 찾아 문제를 해결하였다.배열 ary[20][20]에서 ary[n][n] = ary[n - 1][n] + ary[n][n - 1]이다.for 문을 사용하여 ary[x][0]과 ary[0][x]의 값을 모두 1로 설정하였다.그리고 또 다른 for 문을 사용하여 찾은 규칙성을 바탕으로 배열에 값을 채워서 최종적으로 ary[SIZE][SIZE]에 있는 값이 출..