C++/ 다익스트라 알고리즘 (가중치 방향 그래프), 신호 라우팅 문제

 

다익스트라 알고리즘

 

최단경로 문제란 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제이다.

가중치가 없는 그래프의 최단 경로는 bfs를 이용해 찾을 수 있다.

 

최단 경로 문제에서 먼저 유의해야 할 점은 음수 가중치 간선의 존재 유무이다.

그래프에 음수 가중치를 갖는 간선이 존재하면 전체 경로의 길이가 짧아지게 된다.

다익스트라 알고리즘은 음수 가중치 간선이 없다는 가정 하에 동작하게 된다.

 

다익스트라 알고리즘은 bfs와 유사한 형태를 가진 알고리즘으로, 시작점에서 가까운 순서대로 정점을 발견해가는 방식이다.

dfs에서는 큐의 정점의 번호를 넣었지만, 다익스트라에서는 정점의 번호와 함께 해당 정점까지의 최단 거리를 쌍으로

Min-heap 우선순위 큐에 저장하게 된다.

단, bfs와 비슷하게 연결된 정점을 방문하기 때문에 최단 거리는 갱신될 수 있다.

 

가중치 방향 그래프

 

사용된 자료구조

- dist 배열 : 최단 거리를 저장하는 배열

- priority queue Q : dist를 기준으로 최소힙을 구성하는 우선순위 큐

- vector<pair> graph : 현재 정점 기준 연결된 정점과 가중치를 저장하는 벡터 페어

- Edge struct : 우선순위 큐에 들어갈 순서쌍 구조체로, 정점 번호와 가중치 값을 가지고 있다.

 

	1	2	3	4	5
dist	inf	inf	inf	inf	inf

 

dist 배열의 초기화. 어떠한 정점도 방문하지 않았기 때문에 무한대 값으로 초기화 해준다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;

struct Edge(){
    int vex; //정점 번호
    int dis; //정점까지 가는 데 드는 비용
    Edge(int a, int b){
        vex=a;
        dis=b;
    }
    bool operator<(const Edge &b)const{
        return dis>b.dis;
    }
};

int main(){
    priority_queue<Edge> Q;
    vector<pair<int, int> > graph[30];
    int i, n, m, a, b ,c;
    cin>>n>>m;
    vector<int> dist(n+1, 2147000000);
    for(i=1;i<=m;i++){
        cin>>a>>b>>c;
        graph[a].push_back(make_pair(b,c));
    }
    Q.push(Edge(1,0));
    dist[1]=0;
    while(!Q.empty()){
        int now=Q.top().vex;
        int cost=Q.top().dis;
        Q.pop();
        if(cost>dist[now]) continue;
        for(i=0;i<graph[now].size();i++){
            int next=graph[now][i].first;
            int nextDis=cost+graph[now][i].second;
            if(dist[next]>nextDis){
                dist[next]=nexDis;
                Q.push(Edge(next,nextDis));
            }
        }
        for(i=2;i<=n;i++){
            if(dist[i]!=2147000000) cout<<i<<" : " <<dist[i]<<endl;
            else cout<<i<<" : imposible"<<endl;
        }
    }

    return 0;
}

 

우선순위 큐

 

while문이 돌면서 큐는 이런 모습으로 채워질 것이다.

초기에 탐색을 시작할 정점이 1 이기 때문에 (1,0) 이라는 값이 큐에 push 되고,

while문 내부에서 pop() 되어 연결된 정점을 next 값으로 받는다.

코드에 나온대로 dist[next] 값이 next.dis 값 보다 작을 시에 최소값이 새로 갱신되는 방식이다.

 

앞에서 우선순위 큐와 bfs를 열심히 복습하고 나면 별것 아니다.

홧팅~~~

 

 

+ 이 알고리즘을 그대로 이용해서 신호 라우팅 문제를 풀어보았다

algospot.com/judge/problem/read/ROUTING

algospot.com :: ROUTING

문제는 다익스트라 알고리즘에서 가중치를 더하는 것이 아닌 곱하는 것으로 바꾼것 외에는 다른 점이 없었다.

컴파일러로 예제를 넣고 돌렸을 때 답은 정확하게 나왔으나 자꾸 오답이라고 나온다..

어디가 잘못된건지 모르겠다 ㅠㅠ

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stdio.h>
using namespace std;
int t, n, m;
vector<vector<pair<int, double> > > graph;

struct Edge{
    int vex;
    double dist;
    Edge(int a, double b){
        vex=a;
        dist=b;
    }
    bool operator<(const Edge &e)const{
        return dist>e.dist;
    }
};

void dijkstra(){
    vector<double> dis(n+1,2147000000.0);
    priority_queue<Edge> Q;

    int a, b;
	double c;
  
    for(int i=0;i<m;i++){
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b,c));
        graph[b].push_back(make_pair(a,c));
    }

    Q.push(Edge(0,1.0));
    dis[0]=1.0;

    while(!Q.empty()){
        int now=Q.top().vex;
        double cost=Q.top().dist;
        Q.pop();
        if(cost>dis[now]) continue;
        for(int i=0;i<graph[now].size();i++){
            int next=graph[now][i].first;
            double nextDis=cost*graph[now][i].second;
            if(dis[next]>nextDis) {
            	Q.push(Edge(next,nextDis));
				dis[next]=nextDis;
			}
        }
    }
    printf("%.10f\n",dis[n-1]);
}
int main(){
    cin >> t;

    while(t--){
	    cin >> n >> m;
        graph.clear();
        graph.resize(n+1);
        dijkstra();
    }
    return 0;
}

 

소수점 10번째 자리까지 출력하래서 했는데 도대체 뭐가 틀린거지!?!