Dijkstra's Shortest Distance Algorithm

Input: A directed graph with positive, integer edge weights and n vertices.One of the vertices, called start, is specified as the start vertex.

Output: A list of the shortest distances from the start vertex to every other vertex in the graph.

Dijkstra's Shortest Distance Algorithm (2)

The algorithm uses an array of n integers (called distance) and a set of vertices (called allowedVertices). the variables v, allowedSize, and sum are local integer variables. there is some special value ( inf) that we can place in the distance array to indicate that there is no path.

Step 1. Initialize the distance array to contain all inf except distance[start], which is set to 0.

Step 2. Initialize the set of allowed vertices to be the empty set.

Step 3. Compute the distance array:

   for (allowedSize =1; allowedSize < n; allowedSize++)
   {
 		// at this point, allowedVertices contains allowedSize-1 vertices, which are the
		// allowedSize-1 closest vertices to the start vertex. Also, for each vertex v, 
		// distance[v] is the shortest distance from the start vertex  to vertex v,
		// provided that we are considering only permitted paths (i.e., paths where
		// each vertex except the final vertex must be in allowedVertices
	
		Step3a. Let next be the closest vertex to the start vertex, which is not yet in the 
			set allowedVertices.

		Step 3b. Add the vertex next to the set allowedVertices.

		Step 3c. Revise the distance array so that the new vertex (next) may appear
			on permitted paths:

			for (v = 0; v < n; v++)
			if ((v is not an allowed vertex) and (there is an edge from next to v))
			{
				sum = distance[next] + (weight of the edge from next to v);
				if (sum < distance[v]) 
						distance[v] = sum;
			}
	}

Step 4. Output the values in the distance array.

Finding the shortest path is described in the text.

"Discussion: The problem of finding shortest paths in a graph has a surprising variety of applications:

• The most obvious applications arise in transportation or communications, such as finding the best route to drive between Chicago and Phoenix or figuring how to direct packets to a destination across a network.
• Consider the problem of image segmentation, that is, separating two characters in a scanned, bit-mapped image of printed text. We need to find the separating line between two points that cuts through the fewest number of black pixels. This grid of pixels can be modeled as a graph, with any edge across a black pixel given a high cost. The shortest path from top to bottom defines the best separation between left and right.
• A major problem in speech recognition is distinguishing between words that sound alike (homophones), such as to, two, and too. We can construct a graph whose vertices correspond to possible words, with an edge between possible neighboring words. If the weight of each edge measures the likelihood of transition, the shortest path across the graph defines the best interpretation of a sentence.
• Suppose we want to draw an informative picture of a graph. The center of the page should correspond to the ``center'' of the graph, whatever that means. A good definition of the center is the vertex that minimizes the maximum distance to any other vertex in the graph. Finding this center point requires knowing the distance (i.e. shortest path) between all pairs of vertices."
  
  - Shortest Path from The Algorithm Design Manual by Steven S. Skiena

Here's what the Dictionary of Algorithms and Data Structures has to say about Dijkstra's algorithm

Dijkstra's Algorithm and Best-First-Search

 

One more link: Data Structures and algorithms: Dijkstra's Algorithm

Programming assignment.

Find directions in a map.

 

Minimum spanning trees

• Definition - A minimum-weight tree in a weighted graph which contains all of the graph's vertices. (Entry in Dictionary of Algorithms and Data Structures)

• Motivation - "The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn't a tree you can always remove some edges and save money." - ICS 161: Design and Analysis of Algorithms

• Links

• Mathematical Programming
• ICS 161: Design and Analysis of Algorithms
• Minimum Spanning Tree Algorithms
• Data Structures and Algorithms: Graph Algorithms

---

This work is licensed under a Creative Commons License.
Ernest Ackermann Department of Computer Science, Mary Washington College
CPSC 110 | CPSC 321

---

Bibliographic Information:

.