Tüm olası yolları bulmak için dijkstra algoritması nasıl değiştirilir?

Question

Daha önce sorulabileceğini biliyorum ama bulamıyorum. 2 düğüm arasında en kısa yolunu bulmak için iyi çalışan dijkstra algoritmasını aşağıda değiştirmem gerekiyor ancak olası tüm yolları da bulmam gerekiyor. Bunu yapmak nispeten kolay olmalı biliyorum ama şu ana kadar bu kadar basit bir şekilde nasıl yapılacağı konusunda bir fikrim yok . Yönlendirilmiş ağırlıklı grafik kullanıyorum.

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

Tamam, aslında BFS yapmak için Dijkstra sınıfını değiştirdim ve bana olası tüm yolları var.

public void BreadthFirst(Edge graph, LinkedList<String> visited) 
{ 
    LinkedList<String> nodes = graph.adjacentNodes(visited.Last()); 

    // Examine adjacent nodes 
    foreach (String node in nodes) 
    { 
     if (visited.Contains(node)) 
     { 
      continue; 
     } 

     if (node.Equals(endNode)) 
     { 
      visited.AddLast(node); 

      printPath(visited); 

      visited.RemoveLast(); 

      break; 
     } 
    } 

    // In breadth-first, recursion needs to come after visiting adjacent nodes 
    foreach (String node in nodes) 
    {  
     if(visited.Contains(node) || node.Equals(endNode)) 
     { 
      continue; 
     } 

     visited.AddLast(node); 

     // Recursion 
     BreadthFirst(graph, visited); 

     visited.RemoveLast(); 
    } 
} 

Kullanımı böyle olacağını: Ben senin başlık düzenledikten

Dijkstra d = new Dijkstra(_edges, _nodes); 

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

d.BreadthFirst(graph, visited); 

Answer 2

Grafikte olası tüm yolları bulmak için çevrimiçi bulduğum bir çift algoritma. Dijkstra'nın algoritmasını değiştirmiyorlar ama bence istediklerini yapmalılar. https://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph itibaren

---

:

Suresh DFS, MRA çalıştığını net değil dikkat çekti önerdi. İşte bu yorum dizisini takip eden bir çözüm girişimim. Grafiğin, kaynaklardan hedef t'ye olan m kenarları, n düğümleri ve p yolları varsa, aşağıdaki algoritma O ((np + 1) (m + n)) zamanındaki tüm yolları yazdırır. (Özellikle, O (m + n) zamanın, yolun olmadığını fark etmesi zaman alır.)

Fikir çok basittir: Kapsamlı bir arama yapın, ancak kendinizi bir köşeye aldığınızda erken bırakın.

MRA'nın karşı örneği, daha önce kazıma yapmadan, ayrıntılı aramanın p = 1 olsa bile Ω (n!) Zaman harcadığını gösterir: Düğüm t, yalnızca bir bitişik kenara sahiptir ve onun komşusu, tamamının parçası olan düğümdür. (alt) grafik Kn − 1. yol yığını ve çağrı arama (lar) üzerinde

itin s:

İşte

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 

arama yapar kapsamlı arama ve (burada olduğu gibi) DFS tarzında uygulanabilecek sıkışmış veya BFS tarzında . All possible paths in a cyclic undirected graph itibaren

---

:

Sen gibi DFS kullanarak tüm yolları bulabilirsiniz | Vlad tanımladı. Her düğümde hangi düğümlerin görüneceğini bulmak için, her düğümün şimdiye kadar her yolda görünüp görünmediğini belirten bir boole dizisi elde edebilirsiniz. DFS'niz bir yol bulduğunda, her bir tepe noktasından yola çıkmayın ve karşılık gelen dizi değerini false olarak ayarlayın. İşiniz bittiğinde, yalnızca doğru değerleri olan köşe noktaları her yolun içinde görünenler olacaktır.

yalancı kod:

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. 

Ancak bu algoritma çok etkili değildir. Örneğin, n köşe noktalarının tam bir grafiğinde (tüm köşe noktalarının diğerlerine kenarları vardır) yol sayısı n olacaktır! (n faktöriyel).

daha iyi bir algoritma ayrı ayrı tepe her yoldaki varlığını kontrol etmek olacaktır. Her köşe için, kaynaktan bu köşeye gitmeden kaynağından bir yol bulmaya çalışın. Eğer bir tane bulamazsanız, köşe her yolunda görünür.

yalancı kod: Bir yol ararken

// 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; 

Maalesef bu hala üstel kötü durumda bulunmaktadır. Aramayı geniş kapsamlı bir ilk aramaya çevirerek düzeltebilirsiniz. Yanılmıyorsam, bu size O (VE) performans vermeli. sorusunu tartışıyor

---

Diğer bazı makaleler: Kolayca size tüm olası yolları göstermek için Dijkstra değiştiremez

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

Answer 3

. BFS veya DFS aramasını değiştirmeniz gerekir.

Dijkstra'yı değiştirmeye çalışırsanız, sonunda bir BFS veya DFS arama algoritmasıyla sona erersiniz, bu yüzden en iyisi bunun yerine buradan başlayabilirsiniz.

Answer 4

basit yollarını bulmak istiyorsanız, değiştirilmiş BFS'u kullanın (bunları yolda tekrarlamamak için kullanılmış köşe noktalarını hatırlayacaksınız). Tüm yolların bulunması bile mümkün olmayabilir (prosedür sonlanmayacaktır (yani bir algoritma değildir)). Sadece döngü ile grafik hayal edin, tüm düğümler arasında sonsuz yollar var (içerdiği ilmeklerin sayısı farklı ...)