问题描述:

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`

:

- for
`v != s`

,`pi[v]`

is intended to be a node adjacent to`v`

that's on a shortest path from`v`

to`s`

. `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
pi[v] is adjacent to v
```

This check runs in O(V + E) time.