Dijkstra's shortest path algorithm without relaxation

Question

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 to v from the heap (calls it min_path), it has to be smallest weight path to v 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 than min_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 than min_path's weight, so their weights are bigger than min_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
• 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
    }
}

Answer 1

This answer refers to a previous version of the pseudocode, which had a bug. Once reaching a vertex, it doesn't update its weight ever again.

Your algorithm isn't Dijkstra's algorithm. Worse, it doesn't calculate shortest paths. As a simple example, consider a graph with nodes $\{s,a,b,t\}$ and the following edges:

• $s\to a$ with weight 1.
• $s\to b$ with weight 2.
• $a\to t$ with weight 9.
• $b\to t$ with weight 1.

The shortest path from $s$ to $t$ is via $b$, but your algorithm will discover $t$ via $a$ and will therefore output a distance of 10 rather than the correct distance, which is only 3.

Finally, you mention that the space complexity is $O(E)$. In fact, since the heap and set contain vertices rather than edges, it is $O(V)$.

Answer 2

Necroposting, but, y'know. Firstly, yup, it is Dijkstra in all but detail.

I think the pseudocode won't work, though I think you can do the algo without decrease-key, so it is fixable.

Dijkstra did relaxation becasue it was the most obviously efficient approach, given he had mostly arrays and a few bits to work with. To this day that approach almost always beats anything else in the real-world.

Anyway, it looks like instead of relaxing, the vertex is re-added to the heap with the lower value. It then pops out just like you want. BUT, the original zombie copy of the vertex is still in there and will reappear and will get readded to the set later (which you might get away with if the set doesn't over-write) and is then recalculated (which again might be benign as it will duplicate vertices in the heap but with high weights creating yet more zombies).

So to fix it, you need to loop on extract min, throwing away anything already in the set thus avoiding zombie armageddon.