Làm thế nào để sửa đổi thuật toán dijkstra để tìm tất cả các đường dẫn có thể?

Question

Tôi biết rằng có thể được hỏi trước nhưng tôi không thể tìm thấy nó. Tôi cần phải sửa đổi thuật toán dijkstra dưới đây hoạt động tốt để tìm kiếm đường dẫn ngắn nhất giữa 2 nút nhưng tôi cần phải tìm tất cả các đường dẫn có thể. Tôi biết điều này tương đối dễ thực hiện nhưng cho đến nay tôi không có ý tưởng cách thực hiện cách đơn giản nhất này. Tôi đang sử dụng đồ thị có trọng số trực tiếp.

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, tôi đã thực sự sửa đổi lớp Dijkstra để làm BFS và nó đã cho tôi tất cả các tuyến đường có thể. Tôi thêm phương pháp này:

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(); 
    } 
} 

Cách sử dụng sẽ là như thế này:

Dijkstra d = new Dijkstra(_edges, _nodes); 

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

d.BreadthFirst(graph, visited); 

Answer 2

Dưới đây là một vài thuật toán tôi tìm thấy trực tuyến để tìm tất cả các đường dẫn có thể có trong biểu đồ. Họ không sửa đổi thuật toán của Dijkstra, nhưng tôi nghĩ họ nên làm những gì bạn muốn.

---

Từ https://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph:

Suresh gợi ý DFS, MRA chỉ ra rằng nó không phải là rõ ràng rằng hoạt động. Đây là nỗ lực của tôi tại giải pháp sau chuỗi nhận xét đó. Nếu đồ thị có m cạnh, n nút và đường dẫn p từ nguồn s đến đích t, ​​thì thuật toán dưới đây sẽ in tất cả các đường dẫn trong thời gian O ((np + 1) (m + n)). (Cụ thể, phải mất thời gian O (m + n) để thông báo rằng không có đường dẫn.)

Ý tưởng rất đơn giản: Thực hiện tìm kiếm đầy đủ, nhưng bảo lãnh sớm nếu bạn đã vào được một góc.

Nếu không có chi tiết sớm, ví dụ phản đối của MRA cho thấy tìm kiếm đầy đủ chi tiêu Ω (n!) Ngay cả khi p = 1: Nút t chỉ có một cạnh liền kề và hàng xóm của nó là nút s. (biểu đồ phụ) Kn − 1.

Đẩy s trên con đường ngăn xếp và gọi tìm kiếm (s):

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 

đây tìm kiếm thực hiện tìm kiếm đầy đủ và bị mắc kẹt có thể được thực hiện trong phong cách DFS (như ở đây) hoặc theo kiểu BFS .

---

Từ All possible paths in a cyclic undirected graph:

Bạn có thể tìm thấy tất cả các đường dẫn sử dụng DFS như | Vlad mô tả. Để tìm các nút nào xuất hiện trong mọi đường dẫn, bạn chỉ có thể duy trì một mảng các boolean cho biết liệu mỗi nút có xuất hiện trong mọi đường dẫn cho đến nay hay không. Khi DFS của bạn tìm thấy một đường dẫn, đi qua từng đỉnh không nằm trong đường dẫn và đặt giá trị mảng tương ứng thành false. Khi bạn thực hiện xong, chỉ các đỉnh có giá trị đúng sẽ là các đỉnh xuất hiện trong mọi đường dẫn.

Mã giả:

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. 

Tuy nhiên, thuật toán này không phải là rất hiệu quả. Ví dụ, trong một đồ thị đầy đủ của n đỉnh (tất cả các đỉnh có cạnh cho tất cả các đỉnh khác) số lượng đường dẫn sẽ là n! (n giai thừa).

Thuật toán tốt hơn là kiểm tra sự tồn tại trong mọi đường dẫn của mỗi đỉnh riêng biệt. Đối với mỗi đỉnh, cố gắng tìm một đường đi từ nguồn đến bồn rửa mà không đi đến đỉnh đó. Nếu bạn không thể tìm thấy một, đó là bởi vì đỉnh xuất hiện trong mọi con đường.

Mã giả:

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

Thật không may, điều này vẫn có trường hợp xấu nhất theo cấp số nhân khi tìm kiếm một con đường. Bạn có thể sửa lỗi này bằng cách thay đổi tìm kiếm thành tìm kiếm rộng đầu tiên. Nếu tôi không nhầm, điều này sẽ cho bạn hiệu suất O (VE).

---

Một số bài viết khác thảo luận câu hỏi:

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

Answer 3

Bạn có thể không dễ dàng sửa đổi Dijkstra để cho bạn thấy tất cả các đường dẫn có thể. Bạn cần phải sửa đổi tìm kiếm BFS hoặc DFS.

Nếu bạn cố gắng sửa đổi Dijkstra, cuối cùng, bạn sẽ kết thúc bằng thuật toán tìm kiếm BFS hoặc DFS, vì vậy hãy bắt đầu từ đó tốt nhất.

Answer 4

Nếu bạn muốn tìm tất cả đơn giản đường dẫn, thay vì sử dụng sửa đổi BFS (bạn sẽ nhớ các đỉnh được sử dụng để không lặp lại chúng trong đường dẫn). Việc tìm kiếm tất cả các đường dẫn có thể không khả thi (thủ tục sẽ không chấm dứt (tức là nó không phải là một thuật toán)). Chỉ cần hình dung đồ thị với chu trình, có các đường dẫn vô hạn giữa tất cả các nút (khác nhau về số vòng lặp chứa ...)