벨만포드(Bellman-Ford)알고리즘이란? : 최단 경로(shortest path)를 찾는 알고리즘 중 하나
다익스트라(Dijkstra)알고리즘과차이점 : 다익스트라는 음의 가중치가 있는 그래프에서 작동하지 않으며 벨만포드는 이러한 그래프에서 작동한다. : 벨만포드는 다익스트라보다 단순하며 분산 시스템에 적합하다. : 다익스트라 알고리즘은 Greedy 알고리즘이며 시간 복잡도는 O((V+E)LogV)이다. 벨만포드의 시간 복잡도는 O(V * E)로 다익스트라보다 더 크다.
벨만포드 알고리즘예시 ↓위에 제시된 예시의 벨만포드 알고리즘 과정을 그림으로 표현↓
벨만포드 알고리즘코드
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u;
int v;
int w;
};
struct Graph {
int V;
int E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void printArr(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void BellmanFord(struct Graph* graph, int u) {
int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++){
dist[i] = INT_MAX;
}
dist[u] = 0;
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].u;
int v = graph->edge[j].v;
int w = graph->edge[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].u;
int v = graph->edge[i].v;
int w = graph->edge[i].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
printf("Graph contains negative w cycle");
return;
}
}
printArr(dist, V);
return;
}
💻 문제풀이
Leetcode 743번
문제 n개의 노드로 구성된 네트워크에 1부터 n까지 레이블이 지정됩니다. 또한 지시된 에지 시간 [i] = (ui, vi, wi)와 같은 이동 시간 목록이 제공됩니다. 여기서 ui는 소스 노드, vi는 대상 노드, wi는 신호가 소스에서 대상으로 이동하는 데 걸리는 시간입니다. 우리는 주어진 노드 k에서 신호를 보낼 것이다. n개의 모든 노드가 신호를 수신하는 데 걸리는 최소 시간을 반환합니다. n개의 노드가 모두 신호를 수신할 수 없는 경우 -1을 반환합니다.
예제
다익스트라를 이용한 풀이
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
vector<int> dist(N+1, INT_MAX);
vector<vector<pair<int,int>>> graph(N+1);
for(auto &edge : times)
graph[edge[0]].push_back({edge[1], edge[2]});
dist[K] = 0;
set<pair<int,int>> s;
s.insert({0,K});
while(!s.empty())
{
pair<int,int> q = *s.begin(); s.erase(*s.begin());
int vertice = q.second;
for(auto &p : graph[vertice])
{
int neighbor = p.first;
int weight = p.second;
if(dist[neighbor] > dist[vertice] + weight )
{
if(s.count({dist[neighbor], neighbor}))
s.erase({dist[neighbor], neighbor});
dist[neighbor] = dist[vertice] + weight;
s.insert({dist[neighbor], neighbor});
}
}
}
int res = INT_MIN;
for(int i = 1; i <= N; i++)
res = max(res, dist[i]);
return res != INT_MAX ? res: -1;
}
};
벨만포드를 이용한 풀이
class Solution
{
public:
int networkDelayTime(vector<vector<int>> ×, int n, int k)
{
int max = 0;
vector<int> dist(n + 1, INT_MAX);
dist[k] = 0;
for (int i = 0; i <= n - 1; i++)
{
for (const auto vertice : times)
{
int u = vertice[0];
int v = vertice[1];
int weight = vertice[2];
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 1 ; i<dist.size();i++)
{
if (dist[i] == INT_MAX)
return -1;
else if (dist[i] > max)
max = dist[i];
}
return max;
}
};
백준 1916번
문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.
입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
