For Dijkstra's Algorithm, at every step, the visited node, v, is done and never visited again (invariant) , the edge to that node v is the min edge.
To show why Dijkstra's Algorithm would not produce a optimized shortest path, let's take this graph with negative edge (A, B) as an example, at the start there are S (source node), A, B, C, D.
Starting at source node S, we would choose the edge (S, B) as the edge weight is shorter.
Node is would be marked done and the edge (S, B) would be set as the min edge from S to B.
Since Dijkstra is a greedy Algorithm, node B is visited and would never be visited again.
But there is a shorter path from S -> A -> B of weight 0. Dijkstra would provide a wrong path since it might not be considered due to the invariant of the algo.
Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated?
It would be slower, keep it only if you need to. If you do that, you are essentially writing the Bellman Ford Algorithm, so I would refer address it as the Bellman Ford Algorithm. It is the original shortest path algorithm.
Assume a graph of V vertices and E edges.
Note that Dijkstra $ O((V + E) log V) $, is slightly faster than Bellman Ford $ O (VE) $, as it is a optimized version of Bellman Ford.
i. Dijkstra is faster than Bellman Ford due to it's invariant. It would only visit each vertex once and the edges it checks would reduce as vertex visited increases, since it assumes the edges it sets would be the best path. Whereas,
ii. Bellman Ford algorithm would run the relax function for V times on E edges. It works by overestimating the length of the path from the starting vertex to all other vertices. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated path. After 1 iteration of relaxing E edges, one edges is the best path.
So if you correctly tweak the program to keep the edge, it would be slower. In algorithm, you often have to trade time and function, time and space, it depends on you.