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$
  • 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 '18 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$ – David Richerby Mar 2 '18 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 '18 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$ – David Richerby Mar 2 '18 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 '18 at 13:58
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$
  • $\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 '18 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$ – Yuval Filmus Mar 2 '18 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$ – Yuval Filmus Mar 2 '18 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 '18 at 4:52
  • $\begingroup$ Unfortunately, interactive debugging of this sort isn't really suitable for this site. $\endgroup$ – Yuval Filmus Mar 2 '18 at 4:53

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.