Dijkstra's shortest path algorithm without relaxation 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) &lt; 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&lt;int[]&gt;[] 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&lt;int[]&gt;[] map, int n, int src, int dst) {
        boolean[] been = new boolean[n];
        // 0: vertex, 1: weight
        PriorityQueue&lt;int[]&gt; pq = new PriorityQueue&lt;&gt;((o1, o2) -&gt; 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
    }
}
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)$.