최단경로

플로이드 와샬(Floyd Warshall)

📔 플로이드 와샬(Floyd Warshall) 란 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. ( 출처: 위키백과 ) 모든 정점에서 모든 정점으로의 최단 경로를 구하는 것! 거쳐가는 정점을 기준으로 구한다. 다이나믹 프로그래밍 기법을 이용 다익스트라의 경우 한 정점에서 모든 정점까지 의 최단 경로 반복문이 3개이므로 시간복잡도는 O(N^3) 이다. 하지만 코드는 매우 간단하다. 📔 플..

다익스트라(dijkstra)

📔 다익스트라(dijkstra) 란 다익스트라를 들어가기 전에... 최단 경로란 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 간선의 가중치가 균일(1)할 경우 BFS를 사용 음의 가중치를 허용하지 않음 하나의 시작 정점에서 끝 정점까지의 최단경로 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 시작 정점(s) 에서 끝 정점(t) 까지의 최단 경로에 정점 x 가 존재한다. 이때, 최단 경로는 s 에서 x 까지의 최단경로와 x 에서 t 까지의 최단경로로 구성된다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다. 아래 코드의 경우 시간복잡도는 O(N^2) 이다. 만약 우선순위큐를 이용하게 된다면 O(NlogN..

[python] 백준 - 1753. 최단경로

문제 해결 1. 방향이 있는 그래프에서 최단거리를 구하는 문제 | 보통 다익스트라 알고리즘을 사용한다. 2. 인접리스트, 가중치 배열, 힙큐를 준비한다. (1) 인접행렬보다 인접리스트가 조금 더 빠르다(?) (2) 가중치 배열: 인덱스 번호에 도착할 때의 가중치를 항상 최솟값으로 업데이트 해준다. (3) 힙큐는 항상 최솟값을 리턴해준다. 3. ex)a - c 와 a- c 로 갈 때의 가중치를 항상 비교하여 최솟값을 넣어줘야 한다. -> selected배열(출발했었는지 확인)을 만들어서 했는데 어짜피 단방향이라 필요가 없었다. python으로 제출 시 시간초과가 나서 pypy로 제출했더니 통과 했다. python으로 통과한 사람과의 코드를 비교해봤는데 차이가없었다..... 후😭 왜때문인지 모르겠다. 소스 ..