Dijkstra Floyd–Warshall
합승 택시 요금
풀이과정
백준의 특정한 최단 경로 문제와 비슷하다고 느꼈다.
다익스트라랑 플로이드-와샬 두 가지 방법으로 풀어보았는데, 플로이드-와샬이 더 효율이 좋았다. 모든 정점에서 모든 정점까지의 최단 거리를 구할 때는 플로이드-와샬, 한 정점에서 다른 정점까지의 최단 거리를 구할 때는 다익스트라를 사용하는 것이 맞는 것 같다.
| 복잡도 | 다익스트라 | 플로이드-와샬 |
|---|---|---|
| 시간복잡도 | 인접행렬 : \(O(V^2)\) 인접리스트 + 우선순위 큐 : \(O(E log V) + O(E)\) |
\(O(V^3)\) |
| 공간복잡도 | 인접행렬 : \(O(V^2)\) 인접리스트 : \(O(V) + O(E)\) |
\(O(V^2)\) |
(1) 정점 간 최단 경로를 모두 구해야 하는 경우
- 간선이 많음 -> 플로이드-와샬
- 간선이 적음 -> 플로이드-와샬(\(O(V^3)\)), 다익스트라 (\(O(E log V) + O(E)\))
(2) 한 정점에서 다른 정점까지의 최단 경로만 구해야 하는 경우
- 간선이 많음 -> 인접행렬 + 다익스트라
- 간선이 적음 -> 인접리스트 + 다익스트라
코드
궁금해서 두 가지 방법으로 모두 풀어보았다.
다익스트라(우선순위 큐)
#include <string>
#include <vector>
#include <queue>
#define MAX 100'000'000
using namespace std;
void dijkstra(vector<pair<int,int>>* edges, vector<int>& dist, int start) {
priority_queue<pair<int,int>> pQ;
pQ.push({0, start});
dist[start] = 0;
int v,w;
while(!pQ.empty()){
w = pQ.top().first;
v = pQ.top().second;
pQ.pop();
if(dist[v] < -w) continue;
for(auto it = edges[v].begin(); it!=edges[v].end();it++){
if(dist[it->first] > dist[v] + it->second){
dist[it->first] = dist[v] + it->second;
pQ.push({-dist[it->first],it->first});
}
}
}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
vector<pair<int,int>> edges[201];
for(int i=0;i<fares.size();i++){
edges[fares[i][0]].push_back({fares[i][1],fares[i][2]});
edges[fares[i][1]].push_back({fares[i][0],fares[i][2]});
}
vector<vector<int>> dist(n+1, vector<int>(n+1, MAX));
for(int i=1;i<=n;i++){
dijkstra(edges, dist[i], i);
}
int answer = MAX;
for(int i=1;i<=n;i++){
if(answer> dist[s][i] + dist[i][a]+ dist[i][b]){
answer= dist[s][i] + dist[i][a]+ dist[i][b];
}
}
return answer;
}
플로이드-와샬
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100'000'000
using namespace std;
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
vector<vector<int>> dist(n+1, vector<int>(n+1, MAX));
for(int i=0;i<fares.size();i++){
dist[fares[i][0]][fares[i][1]] = fares[i][2];
dist[fares[i][1]][fares[i][0]] = fares[i][2];
}
for(int i=1;i<=n;i++) dist[i][i] = 0;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
int answer = MAX;
for (int i = 1; i <= n; i++) {
answer = min(answer, dist[s][i] + dist[i][a]+dist[i][b]);
}
return answer;
}
결과
다익스트라
테스트 1 〉통과 (1.76ms, 3.97MB)
테스트 2 〉통과 (6.56ms, 4.15MB)
테스트 3 〉통과 (3.69ms, 3.98MB)
테스트 4 〉통과 (3.57ms, 3.97MB)
테스트 5 〉통과 (3.57ms, 3.93MB)
테스트 6 〉통과 (3.66ms, 3.96MB)
테스트 7 〉통과 (27.65ms, 8.13MB)
테스트 8 〉통과 (27.16ms, 7.99MB)
테스트 9 〉통과 (14.34ms, 8.09MB)
테스트 10 〉통과 (14.45ms, 8.05MB)
테스트 11 〉통과 (14.35ms, 8.09MB)
테스트 12 〉통과 (19.59ms, 5.83MB)
테스트 13 〉통과 (19.34ms, 5.83MB)
테스트 14 〉통과 (19.48ms, 5.79MB)
테스트 15 〉통과 (19.33ms, 5.77MB)
테스트 16 〉통과 (3.22ms, 3.92MB)
테스트 17 〉통과 (3.17ms, 3.96MB)
테스트 18 〉통과 (3.27ms, 3.97MB)
테스트 19 〉통과 (7.11ms, 3.98MB)
테스트 20 〉통과 (9.79ms, 4.28MB)
테스트 21 〉통과 (9.92ms, 4.27MB)
테스트 22 〉통과 (19.35ms, 5.73MB)
테스트 23 〉통과 (19.09ms, 5.68MB)
테스트 24 〉통과 (19.36ms, 5.75MB)
테스트 25 〉통과 (2.08ms, 3.98MB)
테스트 26 〉통과 (1.64ms, 3.95MB)
테스트 27 〉통과 (10.75ms, 4.16MB)
테스트 28 〉통과 (11.08ms, 4.09MB)
테스트 29 〉통과 (1.23ms, 3.77MB)
테스트 30 〉통과 (1.23ms, 3.9MB)
플로이드-와샬
테스트 1 〉통과 (0.81ms, 3.96MB)
테스트 2 〉통과 (2.66ms, 4.07MB)
테스트 3 〉통과 (5.72ms, 3.82MB)
테스트 4 〉통과 (5.76ms, 3.95MB)
테스트 5 〉통과 (5.73ms, 3.93MB)
테스트 6 〉통과 (5.73ms, 3.96MB)
테스트 7 〉통과 (6.72ms, 7.65MB)
테스트 8 〉통과 (7.02ms, 7.56MB)
테스트 9 〉통과 (6.93ms, 7.59MB)
테스트 10 〉통과 (6.95ms, 7.61MB)
테스트 11 〉통과 (6.89ms, 7.56MB)
테스트 12 〉통과 (6.26ms, 5.54MB)
테스트 13 〉통과 (6.28ms, 5.51MB)
테스트 14 〉통과 (6.28ms, 5.61MB)
테스트 15 〉통과 (6.37ms, 5.44MB)
테스트 16 〉통과 (5.77ms, 3.97MB)
테스트 17 〉통과 (5.74ms, 3.96MB)
테스트 18 〉통과 (5.76ms, 3.96MB)
테스트 19 〉통과 (5.79ms, 3.94MB)
테스트 20 〉통과 (5.88ms, 4.16MB)
테스트 21 〉통과 (5.88ms, 4.14MB)
테스트 22 〉통과 (6.32ms, 5.61MB)
테스트 23 〉통과 (6.31ms, 5.54MB)
테스트 24 〉통과 (6.31ms, 5.56MB)
테스트 25 〉통과 (5.75ms, 3.97MB)
테스트 26 〉통과 (5.73ms, 3.96MB)
테스트 27 〉통과 (5.87ms, 4.02MB)
테스트 28 〉통과 (5.85ms, 4.1MB)
테스트 29 〉통과 (0.78ms, 3.95MB)
테스트 30 〉통과 (0.78ms, 3.95MB)
REFERENCE
플로이드, 다익스트라 알고리즘 비교
다익스트라 알고리즘(Dijkstra)