Given a graph with $n$ vertices and $m$ edges with weights $w_i$ and a starting vertex $v_0$. The task is to find the shortest path from the vertex $v_0$ to every other vertex.
The algorithm from D´Esopo-Pape will work faster than Dijkstra's algorithm and the Bellman-Ford algorithm in most cases, and will also work for negative edges. However not for negative cycles.
Let the array $d$ contain the shortest path lengths, i.e. $d_i$ is the current length of the shortest path from the vertex $v_0$ to the vertex $i$. Initially this array is filled with infinity for every vertex, except $d_{v_0} = 0$. After the algorithm finishes, this array will contain the shortest distances.
Let the array $p$ contain the current ancestors, i.e. $p_i$ is the direct ancestor of the vertex $i$ on the current shortest path from $v_0$ to $i$. Just like the array $d$, the array $p$ changes gradually during the algorithm and at the end takes its final values.
Now to the algorithm. At each step three sets of vertices are maintained:
The vertices in the set $M_1$ are stored in a bidirectional queue (deque).
At each step of the algorithm we take a vertex from the set $M_1$ (from the front of the queue). Let $u$ be the selected vertex. We put this vertex $u$ into the set $M_0$. Then we iterate over all edges coming out of this vertex. Let $v$ be the second end of the current edge, and $w$ its weight.
And of course, with each update in the array $d$ we also have to update the corresponding element in the array $p$.
We will use an array $m$ to store in which set each vertex is currently.
struct Edge {
int to, w;
};
int n;
vector<vector<Edge>> adj;
const int INF = 1e9;
void shortest_paths(int v0, vector<int>& d, vector<int>& p) {
d.assign(n, INF);
d[v0] = 0;
vector<int> m(n, 2);
deque<int> q;
q.push_back(v0);
p.assign(n, -1);
while (!q.empty()) {
int u = q.front();
q.pop_front();
m[u] = 0;
for (Edge e : adj[u]) {
if (d[e.to] > d[u] + e.w) {
d[e.to] = d[u] + e.w;
p[e.to] = u;
if (m[e.to] == 2) {
m[e.to] = 1;
q.push_back(e.to);
} else if (m[e.to] == 0) {
m[e.to] = 1;
q.push_front(e.to);
}
}
}
}
}
The algorithm performs usually quite fast. In most cases even faster than Dijkstra's algorithm. However there exist cases for which the algorithm takes exponential time.