알고리즘 study -26-

<기초 그래프 알고리즘>

• 최단경로 알고리즘
• Strongly Connected Component(그래프 덩어리 몇개?)
• 최소 신장 트리(그래프에서 간선을 제거하여 트리형태로(간선들 합은 최소값을 유지하며))

<최단 경로 알고리즘>

-> A에서 B까지 가는 최단 경로는???

• 다익스트라 알고리즘 : 하나의 정점에서 모든 정점까지의 최단거리를 알 수 있다

• 플로이드 알고리즘 : 모든 정점에서 모든 정점까지의 최단거리를 다 알 수 있다

• 벨만포드 알고리즘 : 하나의 정점에서 모든 정점까지의 최단거리 구한다

벨만포드는 가중치에 음수값 있어도 사용 가능
다익스트라 = 가중치가 모두 양수값이어야 가능

<다익스트라 알고리즘>

-> 정점 X까지 최단거리로 가기 위해서는 그 직전 지점까지도 최단거리로 가야한다!!!

-> x랑 인접한 지점 y1, y2, y3 까지 각각 최단 거리를 구하고
그 다음 x까지의 가중치를 더한 후 각각 비교해서 답을 찾는다

한 점에서 모든 점 까지의 최단거리
= 최단경로 트리

-->> 트리 = 사이클이 없는 그래프

최단경로 트리를 어떻게 만들 것인가?

T(i) = i까지 도달하는 최단거리 (1에서 출발)

1에서 시작하면 우선 1의 간선 중 가중치 낮은 것 먼저 선택
-> 정점6 까지 거리는 1 (출발 정점 1 기준)
-> 정점1 은 자신이 출발점이므로 최단거리 = 0

2까지 최단 거리는 2의 인접한 정점 중 최단거리가 정해진 1,6까지 거리에 각각 2까지의 거리를 더한 것들 중 최소값이다

0 + 3 > 1 + 1 이므로 6에서 오는게 최단거리
-> 정점2까지 최단거리는 1 + 1 = 2

정점 4 기준 인접 정점 중 최단거리가 정해진 정점은 정점2 밖에 없으므로 정점2까지 최단거리에 2-4 가중치를 더한다
-> 정점 4 까지 거리는 2 + 1 = 3 업데이트

정점 3 까지 거리도 2 + 4 = 6으로 우선 업데이트

현재 색칠 안된 것들 중 최소는 3값을 가지는 정점 4이므로 정점 4 확정

정점 4 기준 인접 정점 2를 보면 3 + 1 = 4, 하지만 이미 정점2는 값2를 가지고 있으므로 업데이트x

정점5는 3 + 2 = 5로 업데이트 / 정점5 확정

정점5 기준 확정x 중 최소값을 가지는 것은 3

3이 가지고 있던 값6 과 (5까지의 값 + 6)을 비교
6 < 5+ 6
-> 3까지 거리 6으로 확정

나머지 확정x 인 7 까지 거리 우선 5+9 = 14 로 업데이트

이제 정점3이 기준

정점3 확정이고
정점 8 -> 6 + 4 = 10으로 업데이트

색칠 안된 것들 중 최소 값을 가지는 8로 이동해서 확정

8에서 7 = 10 + 3과 기존 7 값 14를 비교
정점7 -> 13업데이트

(1) 색칠 x 중 최소값 찾기
(2) 색칠하기
(3) 그 다음 뻗어 나가기

<다익스트라 알고리즘 구현>

8 = 정점 개수
11 = 간선 개수
0 = 시작점
6 = 끝점
-> 0에서 6까지의 최단 거리를 알고 싶다!

0 1 3 = 0과 1 이 연결되어 있고 그 가중치는 3 이다

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

using namespace std;

// T[i] = 정점 i 에 도달하는데 걸리는 최단 거리

//  (1) T[i] 중 최솟값을 정한다. 단, 지금까지 최솟값으로 뽑히지 않았던 값들 중
//  (2) 한 index를 최단거리 확정하면 여기서 부터 뻗어나간다
//       index 의 인접 정점 들 중 index 를 거쳐가는 게 더 최단이면 그들의 값을 업데이트 한다

const int MAX = 100;

vector<int> graph[MAX]; // 그래프
vector<int> cost[MAX];  // 간선 가중치

int n, m, start, End; // 정점 개수, 간선 개수, 시작점, 끝점

int Table[MAX];
bool Check[MAX]; // true면 해당 정점은 최단거리 확정
                  // false면 해당 정점은 아직 최단거리 확정되지 않음
int main() {

  scanf("%d %d %d %d", &n, &m, &start, &End);
  
  for(int i = 0; i < m; i++){
    int a, b, c;
    
    scanf("%d %d %d", &a, &b, &c);
    
    graph[a].push_back(b);
    graph[b].push_back(a);
    
    cost[a].push_back(c);
    cost[b].push_back(c);
  }
    //graph[1] : 2 6 8 9    1이 2,6,8,9와 연결
    // cost[1] : 1 1 3 9   1에서 2,6,8,9 까지의 가중치가 각각 1 1 3 9
    
    for(int i = 0; i<n; i++) Table[i] = 999999999;  
    // 테이블 초기에는 매우 큰 값으로 초기화
    
    Table[start] = 0;  // 시작점은 자기자신이므로 최단거리 = 0
    
    for(int i = 0; i<n; i++){  // 정점 전체 개수 만큼 반복
      // (1) 최솟값을 구한다 / 단, 지금까지 최단거리로 확정되지 않은 정점에 대해서
      // (2) 그 최솟값을 갖는 노드로부터 뻗어나간다
      
      int minValue = 999999999;
      int minIndex = -1;
      
      for(int j = 0; j<n; j++){
        if(!Check[j] && minValue > Table[j]){
          // 확정되지 않았으면서 
          minValue = Table[j];
          minIndex = j;
        }
      }
      
      Check[minIndex] = true; // minIndex 노드는 이제 확정 가능
      
      // 이제 minIndex와 인접한 정점들 값 업데이트 여부 체크
      for(int k = 0; k < graph[minIndex].size(); k++ ){
        int Node2 = graph[minIndex][k];  // minIndex와 인접한 정점
        int Cost2 = cost[minIndex][k];
        
        // minIndex---(cost2)---Node2
        
        if(Table[Node2] > Table[minIndex] + Cost2){
          Table[Node2] = Table[minIndex] + Cost2;
        } // minIndex를 거치는게 더 최단거리면 업데이트 해준다
        
      }
      
    }
  
  
  printf("%d\n", Table[End]); // 도착점까지의 최단거리

  return 0;
}