JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Finding the Best Path Using Dijkstra’s Algorithm | Reply
Name
Finding the Best Path Using Dijkstra’s Algorithm

Problem
You need to find shortest paths from a given vertex to all other vertices in a directed weighted graph without edges with negative weight.

Solution
Let’s suppose we need to find shortest paths from some vertex s to all other vertices. Let V be a set of all vertices of the graph and let’s describe an edge going from vertex u to vertex v with weight w as e(u,v,w). Then let d[i] be the length of the best path from vertex s to vertex i. (We will improve these values iteratively.) And let Q be a priority queue, in which vertices are ordered by non-decreasing their d’s. So the solution is like this pseudo-code:
set d[s]=0 and for all i≠s d[i]=∞
set Q=V
while Q is not empty {
	k = first element in Q
	erase from Q its first element
	for all edges e(k,i,w) (going from k) {
		if (d[i]>d[k]+w)
			d[i]=d[k]+w // that’s called relaxing edge e(k,i,w)
	}
}

First of all, why it’s correct, i.e. why we will really have in d[i] lengths of shortest paths from s to i? That’s can be shown by induction: if for every vertex i already extracted from Q d[i] really contains length of the shortest path from s, and if all edges going from all such i’s are relaxed, then there is no such path to the current vertex k from s that is shorter than d[k] and possibly goes through some vertices still contained in Q. (Of course, this is not a strict proving, but we don’t search for any, we just want to explain as simply as possible.)

This picture illustrates working of Dijkstra algorithm. Here those vertices which have already been processed colored in black, the one that is processed right now – in gray, and other in white.

But this pseudo-code omits a pair of important details: how we find all edges going from a given vertex and how we implement priority queue Q? If there can be an edge between any pair of vertices, in other words, if E=O(V2) (where V is the number of vertices and E is the number of edges) there is no better way of implementation than simply store a graph as adjacency matrix and create a boolean array of flags – is corresponding vertex in Q right now, or it isn’t. Then we will find the first element in Q by iterating over all vertices contained in Q and finding the one for which distance to it from s is minimal. Thus it will result in time complexity O(V2). But if E=o(V2), we have a chance to improve time complexity of the algorithm to O(V+E*logV), if we will store for every vertex a list of edges going from it, and use balanced binary tree for our priority queue.

Another common task may be not only finding lengths of paths, but finding paths themself. To do this, we should create an additional array p[i] indicating the vertex predecessing the given in the shortest path, and do relaxing edges in such manner:
if (d[i]>d[k]+w) {
	d[i]=d[k]+w
	p[i]=k
}

And then, if we want to reconstruct the best path for some vertex t, we should go recursively by these p’s to vertex s – somehow like this:
void bestPath (int i, vector<int> &path) {
	if (i!=s) bestPath(p[i],path);
	path.push_back(i);
}
vector<int> path(0);
bestPath(t,path);
Re: Finding the Best Path Using Dijkstra’s Algorithm (response to post by Ferlon) | Reply
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=1e-7;
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(x-xx)+sqr(y-yy));
}
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[n-1][i]>mt) ++i;
		if (i==c) return -1; else return i;
	}
};

In some sense Dijkstra’s algorithm is similar to breadth-first 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(V2), 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 Bellman-Ford 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 Floyd-Warshall algorithm with time complexity O(V3), but if a graph is sparse enough (E=o(V2)), you may significantly improve time complexity of an algorithm up to O(V2+V*E*logV) by launching Dijkstra’s algorithm with priority queue based on a balanced binary tree from every vertex, instread of using Floyd-Warshall algorithm.
Re: Finding the Best Path Using Dijkstra’s Algorithm (response to post by Ferlon) | Reply
Fibonacci heap requires O(1) time to update element and O(logN) time to extract minimal element. So time complexity will be O(VlogV + E).

I think everything about heaps/priority queues/balanced trees in Dijkstra should be moved to a single note in discussion section. In other places just write O(V^2) complexity and "extract minimal element from set Q".

Remember that this is a very basic algorithm and most certainly newbies would read it. Do not complicate their lives by heaps:)
Re: Finding the Best Path Using Dijkstra’s Algorithm (response to post by syg96) | Reply
Oh sure, thanks, I've edited the remark about an algorithm with Fibonacci heaps time complexity.

But I think even newcomers are smart enough to realize that for the most of TopCoder problems O(V2+E) is enough and they will not be afraid ;) Anyway, if we describe some general algorithm, we should take care of it that it cannot be misinterpreted as one of its possible realizations. (There was a holy war between me and ibra at this issue in the recipe about Ford-Fulkerson method.)
RSS