ダイクストラが正しいパスを見つけられない

Question

ダイクストラのアルゴリズムを実装して、無向グラフの最大ウェイトパスを見つけました。残念ながら、すべての状況で最良の経路を返すわけではありません。私が間違っていたことを理解する助けとなりました。私はこのコードをあまりにも長く見てきました。 AZDG：

 graph.AddConnection("A", "B", .5); 
     graph.AddConnection("A", "J", .2); 
     graph.AddConnection("A", "F", .63); 
     graph.AddConnection("A", "Z", .92); 
     graph.AddConnection("B", "C", .7); 
     graph.AddConnection("B", "E", .112); 
     graph.AddConnection("C", "D", .1); 
     graph.AddConnection("F", "G", .21); 
     graph.AddConnection("G", "D", .92); 
     graph.AddConnection("J", "G", .56); 
     graph.AddConnection("Z", "D", 0.99); 

は私がする必要がありますGへの最強のパスを見つけようとしています。代わりにAFGを出力しています。

private void ProcessGraph(Graph graph, string startingNode) 
{ 
    bool finished = false; 
    var queue = graph.Nodes.Values.ToList(); 
    while (!finished) 
    { 
     Node nextNode = queue.OrderBy(n => n.DistanceFromStart).FirstOrDefault(
     n => !double.IsPositiveInfinity(n.DistanceFromStart)); 
     if (nextNode != null) 
     { 
      var connections = node.Connections.Where(c => queue.Contains(c.Target)); 
      foreach (var connection in connections) 
      { 
       double distance = node.DistanceFromStart + connection.Distance; 
       if (distance < connection.Target.DistanceFromStart) 
        connection.Target.DistanceFromStart = distance; 
      } 
      queue.Remove(nextNode); 
     } 
     else 
     { 
      finished = true; 
     } 
    } 
} 

EDIT：ケースで誰かがこれを見て、私と同じ過ちを作る：私はちょうど私が私の隣人を注文して実現した重みが0 <

ワットEDIT 2に限定されています減少するのではなく増加する順序で重み付けすることができます。そのため、私のパスは正しくありません。私は次のように変更しました：

queue.OrderByDescending(n => n.DistanceFromStart).FirstOrDefault(
     n => !double.IsPositiveInfinity(n.DistanceFromStart)); 

アルゴリズムは期待通りに動作しています。

Answer 1

すべての重量をwから1.0 - wに変更すると、ダイクストラはすぐに使用できます。

最大パスを見つけるために変換するでも動作させるアルゴリズムを変更することができたとしても、上で述べたように努力するだけで無駄になります。