Limited access

Upgrade to access all content for this subject

You are given a greedy algorithm for finding the shortest paths between a given node and all of the other nodes in the graph. The algorithm works by starting with a set of nodes that only contains the starting node. It then iteratively adds nodes to the starting set of nodes by choosing a node that is not currently i​n the set of established nodes and has the smallest distance value.

A distance value for a node $u$ is the length of the edge connecting node $u$ to its neighboring node $v$ plus node $v$'s distance value. The minimum distance value will come from a neighboring node $v$ that belongs to the current iteration's set of established nodes.

What is the name of this algorithm?

A

Bellman-Ford Algorithm

B

Dijkstra's Algorithm

C

Prim's Algorithm

D

Kosaraju-Sharir Algorithm

Select an assignment template