7

したがって、これと同様の質問を見てきましたが、探しているものとはまったく異なります。ダイクストラのアルゴリズムを変更して、頂点 S (ソース) と頂点 X (目的地) の間の最短パスを返す必要があります。やるべきことはわかったと思いますが、助けてほしいです。これが私が修正した疑似コードです。

 1  function Dijkstra(Graph, source, destination):
 2      for each vertex v in Graph:                                // Initializations
 3          dist[v] := infinity ;                                  // Unknown distance function from 
 4                                                                 // source to v
 5          previous[v] := undefined ;                             // Previous node in optimal path
 6      end for                                                    // from source
 7      
 8      dist[source] := 0 ;                                        // Distance from source to source
 9      Q := the set of all nodes in Graph ;                       // All nodes in the graph are
10                                                                 // unoptimized - thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
13          remove u from Q ;
14          if dist[u] = infinity:
15              break ;                                            // all remaining vertices are
16          end if                                                 // inaccessible from source
17          
18          for each neighbor v of u:                              // where v has not yet been 
19                                                                 // removed from Q.
20              alt := dist[u] + dist_between(u, v) ;
21              if alt < dist[v]:                                  // Relax (u,v,a)
22                  dist[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25              end if
26          end for
27      end while
28  return dist[destination];

コードはウィキペディアから取得され、変更されました: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

これは正しく見えますか？

4

3 に答える 3

4

ダイクストラのアルゴリズムを変更する必要はありません。これは、すべてのペアの最短経路アルゴリズムです。2つの特定のノード間の最短パスを見つけようとしているようです-ダイクストラはこれをうまく処理します。

重み付けされていない無向グラフ用に特別に設計されたものが必要な場合は、BFSを実行することをお勧めします。

于 2012-11-19T05:52:11.263 に答える
4

単一の SOURCE から始まる最短パスを見つけた後、パスを出力するために、その前のパスをバックトラックするために DESTINATION から始める必要があります。

Print-Path(G,s,v)
{
    if(v==s)
        print s;
    else if (pi[v]==NULL)       
        print "no path from "+s+" to "+v;
    else{
        Print-Path(G,s,pi[v])
        print v;
    }
}

上記のコードは、Introduction to Algorithm、MIT Press の厚意によるものです

于 2012-11-19T06:03:22.487 に答える