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