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.
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.
Let's Take A Look best Online Mega Store eBay and Amazon.
Subscribe to:
Post Comments (Atom)
0 comments: