# algorithm - Find a shortest path for a directed graph

There is a directed graph `G = [V ; E]` with edge weights `w(u, v)` for `(u, v) E`.

Suppose the values for `{d[v], [v]}; v V` and claims

that these are the length of the shortest path and the predecessor node in

it for `v V` , how could I verify if this statement is true or false that does not solve the entire shortest path problem from scratch? This is an problem I met with not many ideas in my head ..

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm another link you can use to design your own algorithm is http://algs4.cs.princeton.edu/44sp/

The problem is a bit unclear, but to clarify:

There's a node `s` in your graph, and that for each vertex `v`:

1. for `v != s`, `pi[v]` is intended to be a node adjacent to `v` that's on a shortest path from `v` to `s`.
2. `d[v]` is intended to store the shortest distance from `v` to `s`.

The problem is to verify, given a `pi`, `d`, that they legitimately contain back-edges and minimal distances.

An easily implemented condition that verifies this is as follows:

``````For each vertex v
Either:
v = s and d[v] = 0
Or:
d[pi[v]] = d[v] - 1
d[u] >= d[v] - 1 for each u adjacent to v