#알고리즘_다익스트라(Dijkstra Algorithm) - Java

다익스트라 알고리즘은 하나의 정점에서 다른 정점까지 최단경로를 구하는 알고리즘이다.

** 최단 경로(Shortest Path)문제는 정점 u, v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 것

**다익스트라는 가중치가 양수여야 한다. 음수인 경우에는 벨만포드 알고리즘으로 해결

** 다익스트라는 그리디 기법을 기반으로 하기 때문에 추후에 가중치가 감소를 야기하는 음수를 가진 가중치가 있어서는 안된다. ( 근시적인 관점을 유지하기 때문에 추후에 가중치가 감소하는 것을 고려하지 못함)

** 다익스트라는 그리디 기법 기반, 벨만 포드는 dynamic Programming 이라 생각하면 된다. 즉 모든 경우를 확인할 수 있기에  위와 같은 문제가 발생하지 않는다

 

이 알고리즘의 기본 로직은 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며 최단거리를 갱신하는 것이다.

 

알고리즘 매커니즘

 

• 방문(visit)되어 있지 않은 정점 중에서 Dist의 값이 가장 작은 min 값과 index를 찾는다.
• index를 True로 체크한다.
• index와 연결된 모든 정점을 검사한다.
• 간선을 index, X, Y 라고 했을 때 dist[Y] > d[index] + ad[index][Y]이면 갱신 
• 위 과정을 모든 정점을 수행할때까지 반복한다.

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

import java.util.Scanner;   public class dijkstra {          static int ad[][];     static int dist[];     static boolean visit[];     static int E,V;     static int INF=9999999;          public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                  V = sc.nextInt();         E = sc.nextInt();                  ad = new int[V+1][V+1];         dist = new int[V+1];         visit = new boolean[V+1];                  for(int i=0; i<E; i++) {                 int u = sc.nextInt();                 int v = sc.nextInt();                 int val = sc.nextInt();                 ad[u][v] = ad[v][u] = val;         }         for(int i=1; i<=V; i++) {                 dist[i] = INF;         }                  solve(1, 8);     }       private static void solve(int begin, int end) {         // TODO Auto-generated method stub         dist[begin] = 0;                  String str = "";                  //find min         for(int i=0; i<V; i++) {             int min = 9999;             int index = -1;                          for(int j=1; j<=V; j++) {                 if(visit[j] == false && min > dist[j]) {                     min = dist[j];                     index = j;                 }             }                          visit[index] = true;             str += index + " ";                          for(int k=1; k<=V; k++) {                 if(ad[index][k] != 0 && dist[k] > dist[index] + ad[index][k])                     dist[k] = dist[index] + ad[index][k];             }         }                  for(int i=1; i<=V; i++)             System.out.print(dist[i]+" ");         System.out.println('\n'+str);     } }   Colored by Color Scripter

cs