Djikstra의 최단 경로 알고리즘

Question

Djikstra를 배우고 있는데 Djikstra와는 약간 다른 아이디어를 바탕으로 아래 코드를 준비했습니다. 이제 많은 웹 사이트에서 Extract min 및 boolean 배열을 방문 가장자리로 사용했습니다. 나는 아무 것도 사용하지 않았고 나의 대답도 정확합니다. 내 고의가 작동하지 않는 테스트 케이스 또는 시나리오가 있습니까?

import java.util.*; 
class ShortestPath2 
{ 
static int Ar[][]; 
static int dist[]; 

static int nodes; 
public static void djikstra(int source) 
{ 
LinkedList<Integer> list=new LinkedList<Integer>(); 
dist[source]=0; 

list.add(source); 
while(!list.isEmpty()) 
{ 
source=list.removeFirst(); 

for(int i=0;i<nodes;i++) 
{ 
if(Ar[source][i]!=0) 
{ 

if(dist[i]>dist[source]+Ar[source][i]) 
{ 
dist[i]=Math.min(dist[i],dist[source]+Ar[source][i]); 
list.add(i); 
} 


} 

} 



} 

System.out.println(Arrays.toString(dist)); 
} 

public static void main(String[] args) 
{ 

nodes=9; 

Ar=new int[nodes][nodes]; 
dist=new int[nodes]; 

Arrays.fill(dist,Integer.MAX_VALUE); 



Ar=new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
            {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
            {0, 8, 0, 7, 0, 4, 0, 0, 2}, 
            {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
            {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
            {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
            {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
            {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
            {0, 0, 2, 0, 0, 0, 6, 7, 0} 
           }; 

djikstra(0); 




} 
} 

Answer 1

Dijkstra의 원본 구현은 부정적인 가장자리 (그러나이를 감지 할 수 있음)와 부정적인 순환 문제를 해결하지 못합니다.

이 문제를 해결하기 위해 Bellman Ford Algorithm을 사용할 수 있습니다.

1. 그것은 그것이 마이너스 사이클이인지 아닌지 검출 할 수있다 (그러나주지 않는

2. 네거티브 에지가있는 경우에도 정확한 최단 경로 (그러나 부정적인 사이클)을 수득 할 음의주기가있는 경우 올바른 해결책은, 그래서 더 나은 우리가

Answer 2

Dijkstra 알고리즘의 모든 아이디어는 우선 순위 큐를 사용하고 있습니다. Dijkstra에서 우선 순위 큐를 제거 할 수 없으며 여전히 Dijkstra 알고리즘이라고 부릅니다. 당신이 작성한 것은 방문을 확인하지 않고 BFS입니다. 그래프에 음수 사이클이 있으면 코드가 종료되지 않습니다. 코드는 부정 사이클없이 그래프 a에서 최단 경로를 찾지 만 복잡성은 지수가 될 수 있습니다. 방문한 목록을 제거한 결과로 노드를 반복해서 다시 방문 할 가능성이 있기 때문입니다. 방문한 목록을 코드에 추가하면 우선 순위 큐를 사용하지 않아 코드가 항상 최단 경로를 찾지는 않습니다. 따라서 선형 시간으로 최단 경로를 찾으려면 우선 순위 대기열과 방문 목록이 모두 필요합니다.

A --100---B --100-- I---100---O // A-B, B-I, I-O weight : 100 
|  /\  /\  | // A-C, C-D, ... weight : 1 
C-D-E-F-G H-J-K-L M-N-P-Q-R 

는 예를 들어 당신은 당신의 코드가 O 방문하는 횟수를 확인하기 위해 위의 그래프를 사용할 수 있습니다.