소개글
1. 자바에성 배열의 시작은 `0` 이므로. Vertext의 범위를 0 ~ 4로 잡았습니다.2. 무한대의 값은 MAX=999를 상수로 지정하여 전역에 걸쳐 사용하였습니다.
경로의 중간점 배열인 P[][]에서의 MAX값은 지나가는 곳이 없을때 즉 Null을 표현하였습니다
///////////////////////////////
printTable(VERTEX,W,
컴파일 실행환경
Java, WindowXP본문내용
import java.io.*;class shot{
public static final int VERTEX = 5; //버텍스갯수
public static final int MAX=999; //무한대 or Null
public static void main(String[] args) throws IOException{
int W[][] = { {0,1,MAX,1,5 }, {9,0,3,2,MAX}, {MAX,MAX,0,4,MAX}, {MAX,MAX,2,0,3}, {3,MAX,MAX,MAX,0}};
int D[][] = new int[VERTEX][VERTEX];
int P[][] = new int[VERTEX][VERTEX];
printTable(VERTEX,W,"초기치 Vertex의 배열--W");
floyd(VERTEX,W,D,P);
printTable(VERTEX,D,"거리의 계산 배열 --D");
printTable(VERTEX,P,"중간의 경유점 배열 --P");
BufferedReader in=new BufferedReader(new InputStreamReader( System.in));
System.out.print("경로를 알고싶은 시작점은?");
int start=Integer.parseInt(in.readLine());
System.out.print("경로를 알고싶은 도착점은?");
int end=Integer.parseInt(in.readLine());
path(start,end,P);
}
public static void floyd(int n, int W[][], int D[][], int P[][]){
int i,j,k;
for(i=0 ; i<n ; i++)
for(j=0; j<n; j++)
{ P[i][j] = MAX; D[i][j] = W[i][j]; }
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(D[i][k] + D[k][j] < D[i][j]) { P[i][j]=k; D[i][j]=D[i][k]+D[k][j]; }
}
public static void path(int s,int e,int P[][]){
if(P[s][e] != MAX) {
//P배열에서 중간점이 없는것을 책에서는0 이 PG에서는 MAX=999로 표현
path(s,P[s][e],P);
System.out.println( "Vertex_" + P[s][e] + "-->");
path(P[s][e],e,P);
}
압축파일 내 파일목록
shot.java
shot.class
shot.class
참고 자료
없음프로그램소스 연관자료
이 자료와 함께 구매한 자료
[소스자료]다익스트라 알고리즘 15페이지
JAVA 최단경로 9페이지
[프로그램] 다익스트라 최단거리 5페이지
java 최단 경로 프로그램 0페이지
Edsger Dijkstra의 ShortestPath 알고리즘을 이용해서 최단거리와 최소비용을 구하.. 7페이지