Dijkstra's algorithm: choosing which point to begin with

[nomadreid]

In Dijkstra's algorithm (for an efficient way to find the shortest path between two given vertices, or nodes, in a graph), the only freedom the programmer has is to name which of the two given vertices one begins with. Is there any efficient way to tell which one of the two one should start with? That is, the answer will obviously be the same, but the total computing time, or number of steps, is likely to be different, according to one's choice.

 

[gsal]

You mean, you want to first apply an algorithm to find out where start from and second apply the real algorithm? I guess that is possible if at the end provides savings.

The very first thing the occurs to me is to start on the node with the least number of connections. In any case, have you simply tried running the program and starting from one node and then starting from the other and see if there are real savings?

Is your graph bi-directional? I presume your worry is a moot point for a directional graph where if you want to go from A to B, you would really need to start from A, I guess.

my 2 cents

 

[nomadreid]

Thanks for your 2 cents, gsal. I will now convert it to local currency...:)
Yes, I would ideally first run a program that did not cost too much (in computer time) in order to select which one of the two given points to use as starting points, and then run the full algorithm. I am referring to an undirected (bidirectional) graph. Running the algorithm on a test graph or two to see which one comes out better is not sufficient -- there is no guarantee that the result of a couple of graphs will work on other graphs. Also there may be other factors that how many connections there are at first... I am not convinced that starting with the end with fewest connections is necessarily the best.

 

[gsal]

Well...I just read a bit of the Wikipedia page for Dijkstra's algorightm...I guess I should have done that in the first place...anyway, it does not seem that complicated at all and it is exhaustive; so, I don't know what kind of algorithm you would initially apply just to find out where to start...may as well start applying Dijkstra's right away.

So, I guess that if you start on node A, you get one SPT starting on A; and if you start on B, you get a SPT starting on B...BUT, I presume the path connecting A to B would be exactly the same on both trees.

One thing you COULD do to improve solution time is to cut Dijkstra's loops short...in other words, if all you want is A to B and not the entire tree...as soon as both A and B are in the solved for set, you can quite the do-loops.

 

[nomadreid]

gsal, thanks. Yes, the algorithm could be made more efficient by eliminating loops. But I do not know whether the running time would be significantly different if you started went from A to B or B to A: that is part of the question (such an algorithm as I am searching for would not exist if there were no difference). That is, I would like to know if there is a difference, and if so, what. It is not obvious that there would be a difference, and it is not obvious that there wouldn't, so I am asking. Anyway, while we are on the question of this algorithm, one thing that strikes me is that the algorithm does not take into account what to do when there are two or more points with the same value assignment and both minimal. That is, what if your algorithm, giving the values to the points, gets to the situation where the algorithm has assigned the values (which are distances to the origin along the paths regarded up to that point) to the neighbors of a current node, and there are two points that fulfill the requirement of being a minimum amongst all the values of all the neighbors? It looks as if it would not be very hard to construct a graph that would make the algorithm freeze in indecision.