0
$\begingroup$

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
    }
}
$\endgroup$
6
  • 1
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$
    – Raphael
    Mar 2, 2018 at 9:34
  • $\begingroup$ I don't see any actual question here. There are three question marks but the first two are after declarative statements (i.e., they're not questions). The third is "is this correct?" Essentially, you're asking us to grade your "homework" for you (I know it's not really homework) but that's the sort of thing that will only ever be useful to you. What's the chance that somebody else in the future will be using the same algorithm and have the same doubts about the same proof? $\endgroup$ Mar 2, 2018 at 11:49
  • $\begingroup$ @DavidRicherby Perhaps the way I wrote them made they didn't look like questions but all 3 of them are questions, if you can answer them, please go ahead. My "declarative statements" are just me trying to show my understanding so someone can correct me. And really, people like you are one of the reasons I rarely ask questions online. Yes, I'm asking for my own sake, so what? Nobody's going to spend time to write that long question like I did for someone else's sake. If you don't feel like answering it, just move on. $\endgroup$
    – Leo
    Mar 2, 2018 at 13:41
  • $\begingroup$ Think about what you just wrote. You just said that the only possible motive for making such a post is selfish. OK, fine. Now put yourself in my position. What motivation do I have to read your post? Basically, nothing but altruism. Essentially, you're saying "I don't care about anyone else, but I sure hope that somebody cares enough about me, a total stranger, to help me." Well, good luck with that. $\endgroup$ Mar 2, 2018 at 13:52
  • $\begingroup$ @DavidRicherby So what is your motivation to read and answer any other post? Not sure what's that but when I answer people's questions I just feel like helping them, it makes me feel good when help people, thats it. $\endgroup$
    – Leo
    Mar 2, 2018 at 13:58

2 Answers 2

1
$\begingroup$

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)$.

$\endgroup$
15
  • $\begingroup$ I beg to differ, with that {s, a, b, t} graph, at the beginning, the heap would contains s, then it extracts s, then a and b are added, then a is extracted, then t is added with weight is 10, but the algorithm doesn't end there. After that, b is extracted then t is added again with weight 3, then t with weight 3 is extracted and the algorithm ends there with correct result. $\endgroup$
    – Leo
    Mar 2, 2018 at 4:40
  • $\begingroup$ After you add $t$ once, you skip it when it's reached again due to the if statement on line 9. $\endgroup$ Mar 2, 2018 at 4:41
  • $\begingroup$ Updating the weight of a vertex, like you state in your comment, is relaxation. If you are already doing it, then you do have the relaxation step. $\endgroup$ Mar 2, 2018 at 4:43
  • $\begingroup$ oh you are right the whole time, there is a bug, line 11 has to be right bellow line 6, let me update my post $\endgroup$
    – Leo
    Mar 2, 2018 at 4:52
  • 1
    $\begingroup$ Unfortunately, interactive debugging of this sort isn't really suitable for this site. $\endgroup$ Mar 2, 2018 at 4:53
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.