최단경로 알고리즘 정리 : 다익스트라, 벨만포드, 플로이드-와샬

• 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
  • 다익스트라
    - 음의 가중치로 인한 싸이클 발생 판별 불가능
    - 현재까지 탐색된 정점 집합에서 최단 경로를 가지고 있는 탐색되지 못한 정점을 찾아 탐색한 정점 집합에 추가한다.
    - 그 다음, 탐색된 정점(i)들에 대해 새로 추가한 정점(j)을 거칠 때 발생하는 최단 경로를 업데이트한다.
      : D[i] = min(D[i], D[j] + W[j][i])
    - 반복한다
    - 기본문제
    https://www.acmicpc.net/problem/1753

    1753번: 최단경로

    
    
    
  • 벨만포드
    - 음의 가중치로 인한 싸이클 발생 판별 가능
    - 최단경로는 순환을 포함해서는 안되므로 경로의 길이는 최대 |N-1| 임을 이용한다
    - 즉, 모든 edge에 대해 |V-1|번만큼 최단경로 업데이트를 해준 뒤에, 또 업데이트가 발생하면 음의 가중치가 있다는 것을 이용한다
    

    for(int i=0; i<N-1; i++){
    	for(int j=0; j<edge.size(); j++){
        	int src, dest, cost = src, dest, cost of edge j;
            
            if(D[src] != INF && D[dest] > D[src] + cost)
            	D[dest] = D[src] + cost;
    	}
    }
    
    for(int j=0; j<edge.size(); j++){
        	int src, dest, cost = src, dest, cost of edge j;
            
            if(D[dest] > D[src] + cost)
            	cout << "there is infinite loop\n";
    }​

     
    N : 정점 개수
    V[] : 탐색한 정점 집합
    s : 시작 정점
    W[][] : 인접행렬
    D[] : s부터 다른 정점까지의 최단 경로
• 모든 최단 경로를 구하는 알고리즘 : 플로이드-와샬
  - 모든 점에 대해 중간 정점으로 취했을 때 최단경로가 발생하면 업데이트함으로써, 모든 정점 간 최단 경로를 구하는 알고리즘
  : W[i][j] = min(W[i][j], W[i][k] + W[k][j])
  
  W[][] : 인접행렬
  - 기본문제
  https://www.acmicpc.net/problem/11404
  

  11404번: 플로이드

• 하나의 목적지로가는 모든 최단 경로를 구하는 알고리즘
  - one to all edge graph를 뒤집으면 된다
  
  
• 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 알고리즘
  - 다익스트라 알고리즘보다 비효율적