Algorithms For Dummies

 

   

  PART 3 

 Exploring the World of Graphs

Explaining Dijkstra’s algorithm

Dijkstra’s algorithm requires a starting and (optionally) ending vertex as input. If 

you don’t provide an ending vertex, the algorithm computes the shortest distance 

between the starting vertex and any other vertexes in the graph. When you define 

an ending vertex, the algorithm stops upon reading that vertex and returns the 

result up to that point, no matter how much of the graph remains unexplored.

The algorithm starts by estimating the distance of the other vertexes from the 

starting point. This is the starting belief it records in the priority queue and is set 

to infinity by convention. Then the algorithm proceeds to explore the neighboring 

nodes, similar to a BFS. This allows the algorithm to determine which nodes are 

near and that their distance is the weight of the connecting edges. It stores this 

information in the priority queue by an appropriate weight update.

Naturally, the algorithm explores the neighbors because a directed edge connects 

them with the starting vertex. Dijkstra’s algorithm accounts for the edge direction.

At this point, the algorithm moves to the nearest vertex on the graph based on the 

shortest edge in the priority queue. Technically, the algorithm visits a new vertex. 

It starts exploring the neighboring vertexes, excluding the vertexes that it has 

already visited, determines how much it costs to visit each of the unvisited ver-

texes, and evaluates whether the distance to visit them is less than the distance it 

recorded in the priority queue.

When the distance in the priority queue is infinite, this means that it’s the algo-

rithm’s first visit to that vertex, and the algorithm records the shorter distance. 

FIGURE 9-3: 

The example 

graph becomes 

weighted and 

directed.

---

CHAPTER 9