问题描述:

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.

您可能感兴趣的文章：

- sql server - Backup of database in C# using SMO doesn't work
- python - I need ordered tags in Wagtail
- bash - Pentaho shell throwing an error while I am calling API to download a file
- android - Nearby API disconnection by changing the place
- botframework - micrsosoft bot framework with deep learning
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**