1つの負のエッジで失敗するDijkstraのアルゴリズムの例

Question

Dijkstraのアルゴリズムが正しい出力を生成できないような1つのエッジを除いて、すべてのエッジが正の重みを持つグラフを考えようとしています。

アイデアがうれしいです。

EDIT：
私は反例として、このグラフを見てきましたが、私は理由を理解していません。 頂点Aがキューから最後にポップアウトすると、Relax()のエッジA->Eになります。だから、パスS->A->Eは（請求されたようにそしてないS->B->E）正しいパスである、選択されます

おかげ

Answer 1

ダイクストラは、目標ノードを展開するときに終了します。また、dijkstra（キューではない）のプライオリティキューを使用して、コストの最も少ないノードを展開します。したがって、あなたの例では、Aは決して拡大されません。

open list = [ S cost:0 ] // priortiy queue 
pop S out of open list 
    closed list = [ S cost:0 ] 
    open list = [ B cost:1 ; A cost:5 ] 
pop B out of open list 
    closed list = [ S cost:0 ; B cost:1 ] 
    open list = [ E cost:2 ; A cost:5 ] 
pop E out of open list 
// it's better to terminate when we reach the goal but if we don't 
// it doesn't make any difference we are going to find the shortest path 
// to other nodes 
    closed list = [ S cost:0 ; B cost:1 ; E cost:2 ] 
    open list = [ A cost:5 ] 
pop A out of open list 
    // there isn't any nodes that we can push to open list 
    closed list = [ S cost:0 ; B cost:1 ; E cost:2 ; A cost:5 ] 
    open_list = [] 

ダイクストラは、それはそれはそれへの最短経路を見つける持っていると仮定しているため、それを拡大するとその閉じたリストにノードを押してください。したがって、目標に達すると終了しなくても、それが閉鎖リストにあるため、Aを拡大することはありません。