Dijkstra’s algorithm

Many more problems than you might at first think can be cast as shortest  path problems, making Dijkstra’s algorithm a powerful and general tool.

General Description

Suppose we want to find a shortest path from a given node s to other nodes
in a network (one-to-all shortest path problem)

• Dijkstra’s algorithm solves such a problem

• It finds the shortest path from a given node s to all other nodes in the network.

• Node s is called a starting node or an initial node

• How is the algorithm achieving this?

• Dijkstra’s algorithm starts by assigning some initial values for the distances from node s and to every other node in the network

• It operates in steps, where at each step the algorithm improves the distance values.

• At each step, the shortest distance from node s to another node is
determined

Notation

In what follows:

• d` denotes the distance value of a node `.

• p or t denotes the status label of a node, where p stand for permanent and t stands for temporary.

• cij is the cost of traversing link (i, j) as given by the problem .The state of a node ` is the ordered pair of its distance value d` and its status label.

Algorithm Steps

Step 1. Initialization

• Assign the zero distance value to node s, and label it as Permanent. [The state of node s is (0, p).]
• Assign to every node a distance value of 1 and label them as Temporary. [The state of every other node is (1, t).]
• Designate the node s as the current node.

Step 2. Distance Value Update and Current Node Designation Update

Let i be the index of the current node.
(1) Find the set J of nodes with temporary labels that can be reached from the current node i by a link (i, j). Update the distance values of these nodes.

• For each j 2 J, the distance value dj of node j is updated as follows new dj = min{dj, di +cij}
where cij is the cost of link (i, j), as given in the network problem.

(2) Determine a node j that has the smallest distance value dj among all
nodes j 2 J, find j such that min
j2J
dj = dj .

(3) Change the label of node j to permanent and designate this node as
the current node.

Step 3. Termination Criterion

If all nodes that can be reached from node s have been permanently labeled, then stop - we are done.

If we cannot reach any temporary labeled node from the current node,
then all the temporary labels become permanent - we are done.
Otherwise, go to Step 2.

  Ads:
  Let's Take A Look best Online Mega Store eBay and Amazon. 

0 comments: