CODEWITHSUNDEEP
algorithmsetdijkstra
newbie
newbie

Reputation: 75

Dijkstras Algorithm Sets

I am currently revising for one of my exams and have come accross this question, "Show, step by step, the use of Dijkstra’s algorithm to find the shortest path from the vertex A to each other vertex in the graph. At each step the known and frontier sets should be clearly indicated." I understand how to find the shortest path but I am usnsure of what a frontier set is? Thank you!

Upvotes: 2

Views: 320

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

There are many ways to formulate Dijkstra's algorithm, but the core idea behind most versions is to split the nodes into three groups:

  1. Nodes where you already know the shortest path from the start point. This is initiallt just the start node and grows as the algorithm runs for longer and longer periods of time.

  2. Nodes in the frontier. These are nodes adjacent to nodes in the first group, where you have a guess of the distance to the node but can't necessarily be sure that guess is correct. At each step in the algorithm, you choose the lowest-cost node in the frontier and move it to the group of nodes where you know the shortest path.

  3. Unexplored nodes. These are all the remaining nodes.

If you implement Dijkstra's algorithm with a priority queue, then the frontier nodes are typically the ones in the priority queue. If you maintain a list of candidate distances to nodes and instead pick the cheapest one at each point, the frontier consists of all the nodes whose candidate distance isn't infinity.

Upvotes: 1

Related Questions