?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Easy

Dynamic Programming Solution to the Shortest Path Problem

ALGOR-WCFBJZ

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