我正在阅读以下问题陈述,意在通过动态编程解决:
给定无向图G,其具有N(1 <N <= 1000)个顶点和正权重 . 找到从顶点1到顶点N的最短路径,或说明此路径不存在 . 提示:在每个步骤中,在尚未检查的顶点和找到顶点1的路径的顶点中,取一个具有最短路径的顶点,从顶点1到它,但仍然找到 .
我相信算法应该是这样的
S = starting point
N = ending point
initialize all distances from S to +infinity
unexplored_vertices[] = [all vertex adjacent to S]
for each v in unexplored_vertices[]
calculate new_distance from S to v
if new_distance is better than the former then
store new_distance
closest_to_v = find(unexplored_vertices[], closest_to_S)
unexplored_vertices[].add_front(closest_to_v)
return distance from S for N
无论如何,这与最短路径的方式非常相似Dijkstra's algorithm works .
我的问题是:我的问题陈述是错误的还是声明真的要求(以及提示)Dijkstra的最短路径算法?