Limited access

Upgrade to access all content for this subject

You are given a dynamic programming algorithm for finding the shortest paths between a given node and all other nodes in the graph. The algorithm works by iteratively finding the optimal value for a given node and a given number of edges in the path, starting at 0. The final value will be the optimal value for the node given the possibility of $n - 1$ edges in the path, where $n$ is the number of nodes in the graph.

The optimal value is equal to the minimum of two values. The first value is the optimal value for the same node given one less edge. The second value is the minimum value of the sum of the cost of the edge from this node to another node plus the optimal value for the other node given one less edge.

What is the name of this algorithm?

A

Prim's Algorithm

B

Kruskal's Algorithm

C

Dijkstra's Algorithm

D

Bellman-Ford Algorithm

Select an assignment template