Djikstraの最短経路アルゴリズム

Question

私はDjikstraのことを学んでいます.Djikstraとは少し違う考え方に基づいて以下のコードを用意しました。 今、多くのウェブサイトで、私はExtract minとboolean array of visited edgesの使用を見てきました。 私はnoneを使いましたが、私の答えも正しいです。私のalgoが動作しないテストケースやシナリオはありますか？

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のオリジナルの実装では、負のエッジは検出されますが（検出できます）、負のサイクルの問題は解決されません。

これを解決するには、ベルマンフォードアルゴリズムを使用できます。

1. それは負のサイクルがあるか否かを検出することができる（ただし、与えない

2. 負エッジが存在する場合でも、正しい最短経路（ただし、負のサイクル）を与えますあなたはおそらく、コードレビューではなく、スタックオーバーフローにこれを投稿する必要があり、負のサイクルが非常に良く、我々はコードを終了し、存在する場合、正しい解決策）

Answer 2

Dijkstraアルゴリズムの背後にある全体のアイデアは、優先度キューを使用しています。ダイクストラからプライオリティキューを削除することはできず、それでもダイクストラアルゴリズムと呼ぶことはできません。あなたが書いたのは、訪問したことを確認せずにBFSです。グラフに負の周期がある場合、コードは終了しません。あなたのコードは、負のサイクルなしでグラフaの最短経路を見つけることができますが、複雑さは指数関数的になります。訪問したリストを削除した結果、ノードを何度も何度も再訪する可能性があるためです。訪問したリストをコードに追加すると、プライオリティキューを使用していないため、コードが常に最短パスを見つけるとは限りません。したがって、線形時間で最短経路を見つけるために、優先キューと訪問リストの両方が必要です。あなたはあなたのコードがOを再訪する回数を見るために上のグラフを使用することができます例として

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 

。