负权的单源最短路问题可以使用Dijkstra算法求解。

求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无意义； (2)利用Dijkztra求每一对不同顶点之间的最短路径的算法时间是O(n3)(图用邻接矩阵表示)； (3)Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是( )。【南京理工大学2000一、21(1．5分)】

A．(1)，(2)，(3)

B．(1)

C．(1)，(3)

D．(2)，(3)

A、当图中存在负权边时，Dijkstra算法必定不能求出源点到所有点的最短路

B、Dijkstra算法的使用条件，要求整个图架构与所有边的权重均已知。

C、当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。

D、当图中存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。

A、当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。 When the graph doesn't contain circuit of negative weight, but contains the edge of negative weight. Dijkstra algorithm can't guarantee the correctness of the algorithm.

B、当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。 When the graph doesn't contain edge of negative weight, Dijkstra algorithm can calculate the shortest path of each pair of vertices.

C、当图中存在负权回路时，Dijkstra算法也一定能求出源点到所有点的最短路。When the graph contains the circuit of negative weight, Dijkstra algorithm can certainly calculate the shortest path form the single source to all the vertices.

D、Dijkstra算法不能用于每对顶点间最短路计算。Dijkstra algorithm can't be applied to calculate the shortest path of each pair of vertices.

A、迪杰斯特拉算法

B、贝尔曼-福德算法

C、SPFA算法

D、弗洛伊德算法

A、O(1)

B、O(n)

C、O()

D、O()

什么是单源最短路径问题？