Although I have found a very similar question to what I want to ask here (https://codereview.stackexchange.com/questions/96064/dijkstras-algorithm-without-relaxation), yet I didn't find a satisfactory answer there, hence comes this question.
So I have done competitive programming for fun for a while, whenever I need to find shortest path, I always implement something like this:
For the sake of brevity, this algorithm only finds shortest path's weight from a vertext s
to a vertex d
(instead of all vertices) (assuming there is no negative cycle in the graph of course)
1. Create an empty min heap with comparator is the weight
2. Create an empty set (most of the time hash set)
3. Add s to the heap with weight is 0
4. Add s to the set
5. while (heap is not empty)
6. min = extract min from heap
7. if (min == d) return min.weight
8. add min to set
9. for (v in adj of min)
10. if (set is not already contains v)
11. add v to heap with weight is min.weight + weight(min, v)
I have always believed that this is Dijkstra shortest path algorithm until today when I saw a video of lecture on Dijkstra algorithm from MIT. I realized that I never had the relaxation step in my Dijkstra algorithm.
So I'm really not sure if it is or just a variant of Dijkstra or not even Dijkstra (maybe A*? I'm not sure)? Also, I have used this algorithm in programming contests many times, it always worked, but now I doubt about its correctness?
Yet, half of me still thinks this algorithm is correct because this not very formal proof:
- At a given time, there could be multiple paths to
v
with different weights in the heap, but once we extract first path tov
from the heap (calls itmin_path
), it has to be smallest weight path tov
in all the paths. - For all the other paths to
v
which haven't been added to the heap, they have to have weight more thanmin_path
's weight because: when they are added to the heap, they can only be added after extracting some other paths which have bigger weight thanmin_path
's weight, so their weights are bigger thanmin_path
's weight.
If my algorithm is correct, then I think the running time would be O(ElogV)
and O(E)
of space because:
- The heap can have at most E elements at a given time
- extract min costs
log(E)
<log(V^2)
=2log(V)
=log(V)
- same goes to adding an elmenet to the heap
- extract min costs
- In total,
O(ElogV)
for running time.
So in the end, I believe my algorithm has same running time with standard Dijkstra that has relaxation and decrease key step (that costs logV
), only downside is my algorithm costs O(E)
for space. Is this correct?
UPDATE1: Java sample code
public class Test30 {
public static void main(String[] args) {
List<int[]>[] map = new List[4];
map[0] = Arrays.asList(new int[]{1, 2}, new int[]{2, 2});
map[1] = Arrays.asList(new int[]{3, 9});
map[2] = Arrays.asList(new int[]{3, 1});
System.out.println(dijkstra(map, 4, 0, 3));
}
public static int dijkstra(List<int[]>[] map, int n, int src, int dst) {
boolean[] been = new boolean[n];
// 0: vertex, 1: weight
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
been[src] = true;
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] pop = pq.remove();
int v = pop[0];
int weight = pop[1];
if (v == dst) return weight;
for (int[] i : map[v]) {
if (been[i[0]]) continue;
pq.add(new int[]{i[0], weight + i[1]});
}
}
return -1; // impossible
}
}