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

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示例,底部有拆分)

请注意,要通过最短路径从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

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

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

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

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

例如:

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

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