이 글에서는 자바 기반의 다익스트라 알고리즘을 예제 형태로 소개하여 독자들이 데이터 구조 도메인 알고리즘을 공부하고 학습하는데 도움이 될 것이라고 믿습니다.
Dijkstra는 각 정점과 소스점 v 사이의 경로 길이가 증가하는 순서로 각 정점까지의 최단 경로를 생성하는 알고리즘을 제안했습니다. 즉, 먼저 길이가 가장 짧은 최단 경로를 찾은 다음 이를 사용하여 다음으로 가장 짧은 길이의 최단 경로를 찾는 식으로 소스 지점 v에서 다른 꼭지점까지의 최단 경로를 모두 찾을 때까지 계속됩니다.
코드 구현은 다음과 같습니다.
package com.algorithm.impl; public class Dijkstra { private static int M = 10000; //이 도로는 차단되었습니다. public static void main(String[] args) { int[][] Weight1 = {//인접 행렬 {0, 3,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] 가중치2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println(""+start+"에서 "+i+"까지의 최단 거리는: "+shortPath[i ] ); } 공개 정적 int[] dijkstra(int[][] 가중치, int start) { //유향 그래프의 가중치 행렬과 시작점 번호 start(0부터 번호가 매겨지며 꼭지점은 배열에 저장됨)를 받아들입니다. //시작부터 최단 경로의 길이를 나타내는 int[] 배열을 반환합니다. int n = Weight.length ; //정점 개수 int[] shortPath = new int[n]; //시작점부터 다른 점까지의 최단 경로를 저장합니다. String[] path = new String[n]; 시작부터 다른 지점까지의 경로 문자열 표현 for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] Visited = new int[n] //현재 정점까지의 최단 경로 여부를 표시합니다. 1은 찾았음을 의미합니다. //초기화, 첫 번째 정점을 찾았습니다. shortPath[start] = 0; Visited[start] = 1 for(int count = 1; count < n; count++) { //n-1개의 꼭짓점을 추가하려면 int k = -1; //초기 꼭짓점 start에 가장 가까운 표시되지 않은 꼭짓점을 선택합니다. int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited [i] == 0 && 무게[시작][i] < dmin) { dmin = 무게[시작][i] k = i } //새로 선택한 정점을 최단 경로를 찾았다고 표시하고, 시작하는 최단 경로는 dmin입니다. shortPath[k] = dmin; Visited[k] = 1 //k를 중간 지점으로 하여 경로를 수정합니다. 방문하지 않은 지점의 거리부터 시작 for(int i = 0; i < n; i++) { if(visited[i] == 0 && 가중치[시작][k] + 가중치[k][i] < 가중치[시작] [나]) { 무게[시작][i] = 무게[시작][k] + 무게[k][i]; 경로[i] = 경로[k] + "-->" + i } } } for(int i = 0; i < n; i++) { System.out.println(""+start+"에서 "+i+"까지의 최단 경로는: "+path[i]); System.out.println("=================================="); }}이 프로그램을 실행한 결과는 다음과 같습니다.
0에서 0까지의 최단 경로는: 0-->0 0에서 1까지의 최단 경로는: 0-->1 0에서 2까지의 최단 경로는: 0-->3-->2 최단 경로에서 0에서 3까지: 0-->3 0에서 4까지의 최단 경로: 0-->3-->2-->4==== =================================0에서 0까지의 최단 거리는 0에서 1까지의 최단 거리입니다. 0에서 2까지의 최단 거리: 50 0에서 3까지의 최단 거리: 30 0에서 4까지의 최단 거리: 60