
Discussion A good example of Dijkstra’s algortihm application is TreesCount problem. Actually, as we may note, Dijkstra’s algorithm constructs some tree – a tree of shortest paths. In this problem we need to count all such possible trees. Let’s look at some vertex v. When constructing shortest paths tree, if there are several possible vertices u, such that d[u]+w(u,v)=d[v] (where w(u,v) is the weight of an edge from u to v), we may choose any of those u’s to include an edge from it to v into our tree, so we should just count numbers of such u’s for all v’s (except the vertex 0) and multiply them all. And here is the code:
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int inf=1000000;
const int c=55;
int d[c];
bool b[c];
ll ans;
int n;
class TreesCount {
public:
int count(vector<string> a) {
n=a.size();
int i,j,k;
ll temp;
for (i=0; i<n; ++i) d[i]=inf;
memset(b,0,sizeof(b));
d[0]=0;
while (1) {
k=1;
for (i=0; i<n; ++i) if (!b[i] && (k==1  d[i]<d[k])) k=i;
if (k==1) break;
b[k]=1;
for (i=0; i<n; ++i) if (a[k][i]!='0' && d[i]>d[k]+a[k][i]'0') {
d[i]=d[k]+a[k][i]'0';
}
}
ans=1;
for (i=1; i<n; ++i) {
temp=0;
for (j=0; j<n; ++j) if (a[i][j]!='0') if (d[j]+a[i][j]'0'==d[i]) ++temp;
ans=ans*temp%mod;
}
return ans;
}
};
Another example is BuildingCities problem. Here we should modify an algorithm: any value d[i][p] stores the length of the shortest path to the vertex i, when we can build p additional cities. And every edge will have not only one parameter of weight, but two – its length and number of additional cities needed to build. So we should process all values of p in increasing order, and for every p process all cities in order of increasing their d[i][p]. And here is the code:
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
double d[55][3010];
const int c=3000;
const double inf=1e15;
const double eps=1e7;
bool b[55];
int n;
double sqr(double a) {
return a*a;
}
double dist(double x, double y, double xx, double yy) {
return sqrt(sqr(xxx)+sqr(yyy));
}
int dst(double x, double y, double xx, double yy, int md) {
double d=dist(x,y,xx,yy)eps;
return int(d/md);
}
class BuildingCities {
public:
int findMinimumCities (int md, int mt, vector<int> ax, vector<int> ay) {
int i,j,k,dp,p;
n=ax.size();
memset(b,0,sizeof(b));
for (i=0; i<n; ++i)
for (j=0; j<c; ++j)
d[i][j]=inf;
for (j=0; j<c; ++j) d[0][j]=0;
p=0;
while (1) {
k=1;
while (1) {
for (i=0; i<n; ++i) if (!b[i] && d[i][p]<inf && (k==1  d[i][p]<d[k][p])) k=i;
if (k==1) ++p; else break;
if (p==c) break;
}
if (k==1) break;
b[k]=1;
for (i=0; i<c; ++i)
for (j=0; j<n; ++j) {
dp=dst(ax[k],ay[k],ax[j],ay[j],md);
if (i+dp<c && d[k][i]+dist(ax[k],ay[k],ax[j],ay[j])<d[j][i+dp]) {
d[j][i+dp]=d[k][i]+dist(ax[k],ay[k],ax[j],ay[j]);
}
}
}
i=0;
while (i<c && d[n1][i]>mt) ++i;
if (i==c) return 1; else return i;
}
};
In some sense Dijkstra’s algorithm is similar to breadthfirst search algorithm – a difference is that Dijkstra’s algorithm’s queue needs priorities when BFS’s one doesn’t. In other sense Dijkstra’s algorithm is similar to Prim’s algorithm of constructing minimal spanning tree of a graph – with a difference that in the last one priorities for vertices are not minimal weights of paths to them, but weights of single edges to them.
Of course, you may use Dijkstra’s algorithm not only for finding shortest paths from a given vertex, but for finding shortest path to a given vertex – for this you should just reverse all edges in a graph.
Another remark is about time complexity of an algorithm. In sparse graphs, where E=o(V^{2}), O(V+E*logV) is not the best known variant. If you are so severe that you can implement and use Fibonacci heap as a priority queue, you may get O(V*logV+E) time complexity (but during seven years of programming competitions I haven’t seen any problem requiring such asymptotically good algorithm).
Dijkstra’s algorithm is working only with graphs those don’t contain edges with negative weight. If you have a problem in which edges with negative weight are allowed, you should use BellmanFord algorithm with time complexity O(V*E). Another problem, when edges with negative weights are allowed, but a graph oneself is acyclic, can be solved with time complexity O(V+E) by processing vertices in order determined by topological sorting. And, finally, the problem in which you are needed to find best paths between all pairs of vertices, is typically solved by FloydWarshall algorithm with time complexity O(V^{3}), but if a graph is sparse enough (E=o(V^{2})), you may significantly improve time complexity of an algorithm up to O(V^{2}+V*E*logV) by launching Dijkstra’s algorithm with priority queue based on a balanced binary tree from every vertex, instread of using FloydWarshall algorithm. 