代码之家  ›  专栏  ›  技术社区  ›  Szyszka947

我什么时候可以假设Dijkstra算法中的某个顶点已经完成了最短路径

  •  0
  • Szyszka947  · 技术社区  · 2 年前

    我试着去理解 Dijkstra's algorithm 并试图编写自己的实现,但有些事情我不理解:

    1. 什么时候可以将某个顶点标记为已访问,并确保没有较短的路径到达它?
    2. 在查找两个顶点之间的最短路径时,何时可以停止搜索?

    此外,一些消息来源称使用 decrease-key 而不是将相邻顶点添加到优先级队列中。这意味着什么?它是如何工作的?

    1 回复  |  直到 2 年前
        1
  •  1
  •   lastchance    2 年前

    Djikstra的算法:

    Initialise all distances to "infinity".
    
    Push start onto a priority queue (front of queue will always holdest shortest distance from a finalised node)
    
    Loop:
       Pop front of queue (effectively finalising it) - (desired end point is inaccessible if queue is empty here)
       If it is the desired end point, then done.
       Otherwise add to queue all nodes accessible from that finalised node whose distance could be improved.
    

    考虑下图(@ravenspoint示例,底部有拆分) enter image description here

    请注意,要通过最短路径从A到B:

    B只(明确地)被考虑过一次。

    E从不被访问-您不需要到所有节点的距离。

    #include <iostream>
    #include <fstream>
    #include <sstream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <limits>
    using namespace std;
    
    using NodeType = char;
    
    struct Edge
    {
       NodeType dest;
       double wt;
    };
    bool operator < ( Edge a, Edge b ) { return a.dest < b.dest; }
    
    using Graph  = map< NodeType, set<Edge> >;
    
    //======================================================================
    
    void read( istream &in, Graph &graph )
    {
       graph.clear();
       NodeType a, b;
       double wt;
       while( in >> a >> b >> wt )
       {
          graph[a].insert( Edge{ b, wt } );
          graph[b].insert( Edge{ a, wt } );
       }
    }
    
    //======================================================================
    
    double Dijkstra( Graph &graph, NodeType start, NodeType finish )
    {
       const double LARGE = numeric_limits<double>::max();
    
       // Set all distances from start to infinity
       map<NodeType,double> dist;
       for ( auto n : graph ) dist[n.first] = LARGE;
       dist[start] = 0;
    
       // Create a priority queue that will be sorted by distance from source
       auto further = [&]( NodeType a, NodeType b ){ return dist[a] > dist[b]; };
       priority_queue< NodeType, vector<NodeType>, decltype(further) > Q( further );
    
       // Push all nodes accessible from the start onto the queue
       cout << "Finalised " << start << '\n';                  // Node with smallest currently-accessible distance
       for ( const Edge &edge : graph[start] )
       {
          dist[edge.dest] = edge.wt;
          Q.push( edge.dest );
          cout << "Queued " << edge.dest << '\n';
       }   
    
       // Dijkstra: take the smallest distance amongst those so far accessible and
       // finalise it (i.e. pop it from the front of the queue).
       while( !Q.empty() )
       {
          NodeType n = Q.top();
          cout << "Finalised " << n << '\n';                   // Smallest currently-accessible node
          if ( n == finish ) return dist[n];                   // If at the target then stop
    
          Q.pop();
          for ( const Edge &edge : graph[n] )
          {
             double test = dist[n] + edge.wt;
             if ( dist[edge.dest] > test )                     // If we improve a distance, then push onto queue
             {
                dist[edge.dest] = test;
                Q.push(edge.dest);
                cout << "Queued " << edge.dest << '\n';
             }
          }
       }
    
       // If we get this far then the target is inaccessible
       return -1.0;
    }
    
    //======================================================================
    
    int main()
    {
       istringstream in( "A C 1 \n"
                         "C B 2 \n"
                         "A D 10 \n"
                         "D E 10 \n"
                         "E B 80 \n" );
    // ifstream in( "graph.in" );
    // istream &in = cin;
       char start = 'A', finish = 'B';
    
       Graph G;
       read( in, G );
       double d = Dijkstra( G, start, finish );
       cout << "\nShortest path from " << start << " to " << finish << " is " << d << '\n';
    }
    

    输出:

    Finalised A
    Queued C
    Queued D
    Finalised C
    Queued B
    Finalised B
    
    Shortest path from A to B is 3
    
        2
  •  -1
  •   ravenspoint    2 年前

    当我可以将某个顶点标记为已访问,并确保没有较短的路径到达它时

    你不能。如果稍后找到较短的路径,则会更新前一个顶点和距离。访问状态保持不变。

    如果我在A和B之间寻找最短路径,何时可以停止搜索

    当您访问了每个顶点时。请注意,您不能提前停止,因为谁知道呢,您访问的最后一个顶点可能有一条到B的边,这是最短路径的一部分。

    例如:

    enter image description here

    根据边缘存储的顺序,第一次访问B时,路径长度为100。第二次,它被更新为3。


    您没有提及您使用的编码语言。以下是Dijkstra的C++实现 https://github.com/JamesBremner/PathFinder/blob/f07a29d10b5c14e6c085dd4eb6cb447e24c21eae/src/GraphTheory.cpp#L18-L76