벨만-포드 알고리즘, Bellman-Ford algorithm 구현하기

다익스트라가 가중치가 양수일 때만 최단거리를 찾는 알고리즘이라면

이 벨만-포드 알고리즘은 음수의 가중치도 계산한다고 보면 되겠다.

어렵지 않고.. 그냥 다익스트라를 정점개수-1만큼 돌린다고 생각하면 된다.

**일반적으로 음수의 가중치는 나오지 않으나 간선을 돌아감에도 비용이 줄어든다는 것은

예를 들어 신호가 x만큼 증폭되는 증폭기가 있다고 했을 때 증폭기가 우리가 갈 노드의 수를 줄여준다고도 볼 수 있겠다.

 

알아보자

---

 

다익스트라가 양수가중치만 있을 때 사용하는 알고리즘이라면

벨만 포드 알고리즘은 음수 가중치가 존재해야만 의미있는 알고리즘이다.

알아보자

 

#include <vector>
#include <iostream>
#include <climits>

using namespace std;

//간선을 표현할 Edge
typedef struct Edge
{
    int src;
    int dst;
    int weight;
}E;

//INF (무한대)
const int INF = INT_MAX;

//벨만 포드 알고리즘은 입력으로 [Edge리스트, Vertex 개수, 출발 정점 번호]들을 받는다.
//당연히 거리 값을 계산한 배열을 반환한다.

vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
    vector<int> distance(V, INF);//V크기의 벡터 INF로 초기화
    distance[start] = 0;
    
    //V-1번 반복
    for(int i = 0; i<V-1; i++)
    {
        //간선 전체에 대해서 반복
        for(auto& e : edges)
        {
            //시작점이 INF면 넘어감
            if(distance[e.src] == INF)continue;
            //인접한 정점들의 거리 값이 새로운 경로에 의한 거리 값보다 클 경우
            if(distnace[e.dst] > distance[e.src] + e.weight)
            {
                distance[e.dst] = distance[e.src] + e.weight;
            }
        }
    }
    
    return distance;
}

 

 

앞서 말했듯이 벨만 포드 알고리즘은

음수 가중치를 가지는 간선이 있을 때 사용한다고 했다.

오히려 다익스트라보다 쉬운 것이..

다익스트라는 최단거리 순으로 탐색했다면..?

벨만 포드는 무조건 다 뒤져봐야하기 때문에 쉬워진다.