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

좋아, 실제로 BFS를 수행하도록 Dijkstra 클래스를 수정했으며 모든 가능한 경로를 얻었습니다.

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

사용법은 다음과 같이 될 것이다 : 나는 당신의 제목을 편집 한

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에는 하나의 인접한 모서리 만 있고 그 이웃은 노드 s입니다. (하위) 그래프 (Kn-1)이다. 경로 스택과 전화 검색 (들)에

푸시 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 

검색을 수행하는 철저한 검색 및 (여기로) DFS 스타일로 구현 될 수 붙어 있거나 BFS 스타일 . 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을 사용하십시오 (사용 된 정점이 경로에서 반복되지 않도록 기억할 것입니다). 모든 경로를 찾는 것조차 불가능합니다 (절차가 종료되지 않습니다 (즉, 알고리즘이 아닙니다)). 그냥주기를 가진 그래프를 상상해보십시오. 모든 노드 사이에 무한한 경로가 있습니다 (포함 된 루프 수가 다릅니다 ...)