When is the shortest path to some vertex found in Dijkstra's algorithm?

Question

I've tried to understand Dijkstra's algorithm and attempted to write my own implementation, and there are some things I don't understand:

1. When can I mark some vertex as visited and be sure that there is no shorter path to it?
2. When can I stop searching when looking for the shortest path between two vertices?

What's more, some sources say to use decrease-key instead of adding adjacent vertices to a priority queue. What does that mean and how does it work?

Answer 1

Djikstra's algorithm:

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.

Consider the following graph (@ravenspoint example with bottom line split)

Note that, to get from A to B by the shortest path:

B is only (explicitly) considered once.

E is never visited - you do NOT need the distance to all nodes.

#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';
}

Output:

Finalised A
Queued C
Queued D
Finalised C
Queued B
Finalised B

Shortest path from A to B is 3