すべての可能なパスを見つけるためにdijkstraアルゴリズムを変更するには？

Question

私はそれが既に前に尋ねられるかもしれないことを知っていますが、私はそれを見つけることができません。 私は2つのノード間の最短経路 を見つけるのにうまくいくdijkstraアルゴリズムを修正する必要がありますが、すべての可能なパスも見つけ出す必要があります。 これは比較的簡単に行うべきであることは分かっていますが、これまでのところ私は考え方がありません これを簡単に行う方法。私は有向グラフを使っています。

class Dijkstra 
    { 
     private List<Node> _nodes; 
     private List<Edge> _edges; 
     private List<Node> _basis; 
     private Dictionary<string, double> _dist; 
     private Dictionary<string, Node> _previous; 

     public Dijkstra(List<Edge> edges, List<Node> nodes) 
     { 

      Edges = edges; 
      Nodes = nodes; 
      Basis = new List<Node>(); 
      Dist = new Dictionary<string, double>(); 
      Previous = new Dictionary<string, Node>(); 

      // record node 
      foreach (Node n in Nodes) 
      { 
       Previous.Add(n.Name, null); 
       Basis.Add(n); 
       Dist.Add(n.Name, double.MaxValue); 
      } 
     } 

     /// Calculates the shortest path from the start 
     /// to all other nodes 
     public void calculateDistance(Node start) 
     { 
      Dist[start.Name] = 0; 

      while (Basis.Count > 0) 
      { 
       Node u = getNodeWithSmallestDistance(); 
       if (u == null) 
       { 
        Basis.Clear(); 
       } 
       else 
       { 
        foreach (Node v in getNeighbors(u)) 
        { 
         double alt = Dist[u.Name] + getDistanceBetween(u, v); 
         if (alt < Dist[v.Name]) 
         { 
          Dist[v.Name] = alt; 
          Previous[v.Name] = u; 
         } 
        } 
        Basis.Remove(u); 
       } 
      } 
     } 

     public List<Node> getPathTo(Node d) 
     { 
      List<Node> path = new List<Node>(); 

      path.Insert(0, d); 

      while (Previous[d.Name] != null) 
      { 
       d = Previous[d.Name]; 
       path.Insert(0, d); 
      } 

      return path; 
     } 

    public Node getNodeWithSmallestDistance() 
     { 
      double distance = double.MaxValue; 
      Node smallest = null; 

      foreach (Node n in Basis) 
      { 
       if (Dist[n.Name] < distance)  
       { 
        distance = Dist[n.Name]; 
        smallest = n; 
       } 
      } 

      return smallest; 
     } 


     public List<Node> getNeighbors(Node n) 
     { 
      List<Node> neighbors = new List<Node>(); 

      foreach (Edge e in Edges) 
      { 
       if (e.Origin.Equals(n) && Basis.Contains(n)) 
       { 
        neighbors.Add(e.Destination); 
       } 
      } 

      return neighbors; 
     } 

     public double getDistanceBetween(Node o, Node d) 
     { 
      foreach (Edge e in Edges) 
      { 
       if (e.Origin.Equals(o) && e.Destination.Equals(d)) 
       { 
        return e.Distance; 
       } 
      } 

      return 0; 
     } 


     public List<Node> Nodes 
     { 
      get { return _nodes; } 
      set { _nodes = value; } 
     } 

     public List<Edge> Edges 
     { 
      get { return _edges; } 
      set { _edges = value; } 
     } 

     public List<Node> Basis 
     { 
      get { return _basis; } 
      set { _basis = value; } 
     } 

     public Dictionary<string, double> Dist 
     { 
      get { return _dist; } 
      set { _dist = value; } 
     } 

     public Dictionary<string, Node> Previous 
     { 
      get { return _previous; } 
      set { _previous = value; } 
     } 
    } 
} 

static void Main(string[] args) 
     { 
//Nodes initialisation goes here 

Dijkstra d = new Dijkstra(_edges, _nodes); 
d.calculateDistance(_dictNodes["A"]); 
List<Node> path = d.getPathTo(_dictNodes["C"]); 
} 

Answer 1

OK、私は実際にBFSを行うためにDijkstraクラスを修正しました。私は、このメソッドを追加しました：私はあなたのタイトルを編集した

Dijkstra d = new Dijkstra(_edges, _nodes); 

LinkedList<String> visited = new LinkedList<string>(); //collecting all routes 
visited.AddFirst(start); 

d.BreadthFirst(graph, visited); 

Answer 2

ここでは、グラフで考えられるすべてのパスを見つけるためにオンラインで見つかったカップルアルゴリズムを示します。彼らはDijkstraのアルゴリズムを変更していませんが、とにかくあなたが望むことをやるべきだと思います。

---

https://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graphから：

スレシュは、DFSを提案し、MRAはそれが動作することは明らかではないことを指摘しました。このコメントのスレッドに続く解決策に私の試みがあります。グラフがソースsからターゲットtまでのm個のエッジ、n個のノード、およびp個のパスを有する場合、以下のアルゴリズムは時間O（（np + 1）（m + n））のすべてのパスをプリントする。 （特に、経路がないことに気付くにはO（m + n）時間かかる）

アイデアは非常に単純です。徹底的な検索を行いますが、あなたがコーナーに入った場合は早めに退くこと。

MRAの反例では、p = 1であっても徹底的な検索がΩ（n！）時間を費やすことを示しています。ノードtに隣接エッジが1つしかなく、その隣接ノードはノードsであり、 （下）グラフKn-1を示す。

プッシュのパス・スタック上と検索（複数可）を呼び出します。

path // is a stack (initially empty) 
seen // is a set 

def stuck(x) 
    if x == t 
    return False 
    for each neighbor y of x 
    if y not in seen 
     insert y in seen 
     if !stuck(y) 
     return False 
    return True 

def search(x) 
    if x == t 
    print path 
    seen = set(path) 
    if stuck(x) 
    return 
    for each neighbor y of x 
    push y on the path 
    search(y) 
    pop y from the path 

ここで検索が徹底的に検索し、立ち往生（ここでのように）またはBFSスタイルでDFSのスタイルで実装することができません。

---

All possible paths in a cyclic undirected graphから：

あなたは次のようにDFSを使用して、すべてのパスを見つけることができます|ヴラドを説明。すべてのパスにどのノードが表示されているかを調べるには、これまでの各パスに各ノードが現れているかどうかを示すブール値の配列を維持するだけです。 DFSがパスを見つけたら、パスにない各頂点を通り、対応する配列値をfalseに設定します。完了すると、値がtrueの頂点だけがすべてのパスに現れる頂点になります。

擬似コード：

int source; 
int sink; 
int nVerts; 
bool inAllPaths[nVerts]; // init to all true 
bool visited[nVerts]; // init to all false 
stack<int> path; // init empty 

bool dfs(int u) 
    if (visited[u]) 
    return; 
    if (u == sink) 
    for i = 0 to nVerts-1 
     if !stack.contains(i) 
     inAllPaths[i] = false; 
    return true; 
    else 
    visited[u] = true; 
    stack.push(u); 
    foreach edge (u, v) 
     dfs(v); 
    stack.pop(); 
    visited[u] = false; 
    return false; 


main() 
    dfs(source); 
    // inAllPaths contains true at vertices that exist in all paths 
    // from source to sink. 

しかし、このアルゴリズムは非常に効率的ではありません。たとえば、n個の頂点の完全なグラフ（すべての頂点が他のすべての頂点にエッジを持つ）では、パスの数はn！ （n階乗）。

より良いアルゴリズムは、各頂点のすべてのパスでの存在を別々にチェックすることです。各頂点に対して、その頂点に行くことなく、ソースからシンクまでのパスを見つけようとする。見つけられない場合は、頂点がすべてのパスに表示されるためです。

擬似コードは：パスを検索するときに

// Using the same initialisation as above, but with a slight modification 
// to dfs: change the foreach loop to 
foreach edge (u, v) 
    if (dfs(v)) 
    return true; // exit as soon as we find a path 

main() 
    for i = 0 to nVerts-1 
    set all visited to false; 
    if (inAllPaths[i]) 
     visited[i] = true; 
     if (dfs(source)) 
     inAllPaths[i] = false; 
     visited[i] = false; 

残念ながら、これはまだ指数最悪の場合があります。これを修正するには、検索を幅優先検索に変更します。私が間違っていないなら、これはあなたにO（VE）のパフォーマンスを与えるはずです。

---

質問を議論するいくつかの他の記事：

algorithm to enumerate all possible paths
Find all paths between two graph nodes

Answer 3

あなたは簡単にあなたにすべての可能なパスを表示するようにダイクストラを変更することはできません。 BFSまたはDFS検索を変更する必要があります。

Dijkstraを修正しようとすると、最後にBFSまたはDFS検索アルゴリズムで終了するので、代わりにそこから開始するのが最適です。

Answer 4

すべてが簡素なのパスを見つけたい場合は、修正されたBFSを使用してください（使用した頂点がパス内で繰り返されないように覚えています）。すべての経路の発見も可能ではない（手順は終了しない（すなわち、アルゴリズムではない））。ちょうどサイクルのグラフを想像して、すべてのノード間に無限のパスがあります（含まれるループの数が異なります...）