다익스트라 알고리즘(Dijkstra algorism)

다익스트라 알고리즘이란, 하나의 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘입니다. 

단, 조건은 모든 정점이 양의 가중치를 갖고 있어야 합니다. 

/*
(정점 개수, 간선 개수, 시작점, 끝점)
(정점1, 정점2, 가중치)
..
..
..
..
(정점1, 정점2, 가중치)
8 11 0 6 
0 1 3
0 5 1
1 2 4
1 3 1
1 5 1
2 4 6
2 6 9
2 7 4
3 4 2
4 6 9
6 7 3
*/
/*
T[i] : 정점 i에 도달하는 데 걸리는 최단거리
for i = 0 ~n 
(1) T[i] 중 최솟값을 정한다. 단, 지금까지 최솟값으로 뽑히지 않았던 값들 중
(2) index로 부터 뻗어 나간다. T[index] + cost
*/
#include <iostream>
#include <vector>
#define MAX 100
 
using namespace std;
 
vector <int> graph[MAX];
vector <int> cost[MAX]; // 간선의 가중치
 
int n, m, start, end2;
 
int Table[MAX];
bool Check[MAX]; //ture : 이미 i 는 최단거리가 확정되었다.
                //false: 아직 i는 최단거리가 확정되지 않았다
int main(){
  cin>>n>>m>>start>>end2; //정점, 간선, 시작, 끝
  
  for(int i = 0; i<m; i++){
    int a, b, c; //a와 b가 연결, c 가중치
    
    cin>>a>>b>>c;
    
    graph[a].push_back(b);
    graph[b].push_back(a);
    
    cost[a].push_back(c);
    cost[b].push_back(c);
  }
  
  for(int i = 0; i<n; i++) Table[i] = 98798798;
  Table[start] = 0; //시작 점은 최단거리가 0, 나머지는 모르니까 큰 값으로 초기화
  
  for(int i=0; i<n; i++){
    //(1) 최솟값을 구한다. 단, 지금까지 최단거리로 확정되지 않았던 정점에 대해서.
    //(2) 그 최솟값을 갖는 노드로부터 뻗어나간다.
    int minValue = 98798798, minIndex = -1; //minValue : 최솟값을 받는 변수
    for(int j = 0; j<n; j++){
      if(!Check[j]&&minValue>Table[j]){
        minValue = Table[j];
        minIndex = j;
      }
    }
    Check[minIndex] = true;
    
    for(int j=0; j<graph[minIndex].size(); j++){ //인접리스트를 돌겠다
      int Node2 = graph[minIndex][j];
      int Cost2 = cost[minIndex][j];
      
      if(Table[Node2] > Table[minIndex] + Cost2){
        Table[Node2] = Table[minIndex] + Cost2;
      }
    }
  }
  
  cout<<Table[end2];
  return 0;
}