当前位置: 动力学知识库 > 问答 > 编程问答 >

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

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

分享给朋友:
您可能感兴趣的文章:
随机阅读: