Dijkstra 알고리즘
그림 의 모든 점 에서 가장 짧 은 경 로 를 지정 하도록 권한 이 없 는 그림 을 보 여 줍 니 다.
먼저, 우 리 는 인접 행렬 c, c [i] [j] 를 정의 하여 정점 i 에서 정점 j 까지 의 가중치 를 나타 내 고 1 차원 배열 prev [] 로 지정 한 노드 의 부모 노드 를 기록 합 니 다. 출력 경로 의 궤적 이 필요 하지 않 으 면 이 배열 을 사용 할 필요 가 없습니다.모든 노드 가 접근 되 었 는 지 vis 의 boolean 배열 로 저장 합 니 다.지정 한 정점 에서 가장 짧 은 경 로 를 dist [] 배열 로 저장 합 니 다.
1. 정점 v 를 지정 하여 각 정점 에 사 이 드 연결 이 있 는 지 확인 하고 검색 하 는 과정 에서 vis 배열 을 false (자바 는 이 단 계 를 생략 합 니 다) 로 초기 화 합 니 다. 두 정점 사이 에 사 이 드 연결 이 있 으 면 prev [i] = v;dist [v] = 0, vis [v] = true;
2. 하나의 순환 으로 남 은 n - 1 개의 정점 에서 지정 한 정점 까지 의 최 단 로 를 찾 습 니 다.dist 배열 에서 지정 한 정점 에 접근 하지 않 은 가장 짧 은 경 로 를 찾 은 다음 에 이 정점 u 를 기록 하고 이 정점 의 vis 를 true 로 설정 합 니 다.
3. 두 번 째 단계 에서 찾 은 정점 u 에서 정점 u 와 연결 되 고 방문 되 지 않 은 정점 을 찾 은 다음 에 이 정점 u 라 는 경로 에서 정점 v 에 도착 하 는 거 리 를 계산 합 니 다.
if(!vis[j]&&c[u][j]>0) {
int tempDis = dist[u] + c[u][j];
if(tempDis<dist[j]) {
dist[j] = tempDis;
prev[j] = u;
}
}
전체 코드 는 다음 과 같 습 니 다:
public class Dijkstra {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] c = {
{0, 10, 0, 30, 100},
{10, 0, 50, 0, 0},
{0, 50, 0, 20, 10},
{30, 0, 20, 0, 60},
{100, 0, 10, 60, 0}
};
dijkstra(0, c);
}
public static void dijkstra(int v, int[][] c) {
int[] dist = new int[c.length];
int[] prev = new int[c.length];
boolean[] vis = new boolean[c.length];
for(int i = 0; i < dist.length; i++) {
dist[i] = Integer.MAX_VALUE;
}
for(int i = 0; i < dist.length; i++) {
dist[i] = c[v][i] == 0 ? Integer.MAX_VALUE : c[v][i];
if(dist[i] > 0) {
prev[i] = v;
}
}
dist[v] = 0;
vis[v] = true;
prev[v] = -1;
for(int i = 1; i < dist.length; i++) {
int curMin = Integer.MAX_VALUE;
int u = 0;
//
for(int j = 0; j < dist.length; j++) {
if(!vis[j] && dist[j] < curMin) {
curMin = dist[j];
u = j;
}
}
// vis[u] = true, u
vis[u] = true;
// u , u v
for(int j = 0; j < dist.length; j++) {
if(!vis[j] && c[u][j] > 0) {
int tempDis = dist[u] + c[u][j];
if(tempDis < dist[j]) {
dist[j] = tempDis;
prev[j] = u;
}
}
}
}
// ........
for(int i = 0; i < dist.length; i++) {
System.out.print(dist[i] + " ");
}
System.out.println();
for(int i = 0; i < dist.length; i++) {
System.out.print(prev[i] + " ");
}
System.out.println();
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.