Dijkstra's Algorithm

Given a weighted graph G and a pair of vertices (s and d), the shortest path problem seeks to find a path from s to d in this graph such that the sum of the weights of the edges along this path is minimized. One famous algorithm for this problem is Dijkstra's Algorithm, which not only finds the shortest path from an origin (s) to a destination (d), but finds the shortest path from (s) to all other vertices (v) in the graph G. The algorithm proceeds as follows:

Dijkstra's Algorithm

  • Initially we have an empty path tree T, and assume that the distance to every vertex in the graph has some maximum cost, say infinity, i.e. w(v) = infinity for all v in V.
  • Add the node s to the tree, and give the associated path cost a value of zero, i.e. w(s) = 0.
  • Find the edge which is adjacent to T that adds the vertex whose cost is minimum, i.e. we look for an e = (u, v) such that u is in T, and v is not in T and w(u) + cost(u, v) < w(v) is minimum. If no such edge exists go to 5.
  • Add the corresponding edge and vertex to the tree, and update the weight vector of the vertex v. Go to 3.
  • The path tree T now represents the shortest path from the vertex s to all other vertices reachable in the graph G. The weight vector w represents the costs of these paths. 0

    Show Work?
    your browser does not support the canvas tag


  • Recent Updates

  • 06-03-2017 Tarjan's Strongly Connected Components Algorithm
  • 03-20-2017 Longest Common Subsequence
  • 10-27-2016 Independent Set Puzzles
  • 06-28-2016 Lets Learn About XOR Encryption
  • 06-15-2016 Discrete-time Markov Chains
  • 03-01-2016 Topological Sort
  • 01-21-2016 The RSA Algorithm
  • 11-20-2015 How To Take Notes in Math Class
  • 10-28-2015 The Depth-First-Search Algorithm
  • 10-28-2015 The Breadth-First-Search Algorithm
  • 09-23-2015 ID3 Algorithm Decision Trees
  • 07-08-2015 Clique Problem Puzzles
  • 06-25-2015 Unidirectional TSP Puzzles
  • 04-04-2015 Learn About Descriptive Statistics
  • 02-19-2015 Slope Formula
  • 01-15-2015 Interactive Midpoint Formula
  • 12-18-2014 Triangle Sum Puzzle
  • 12-02-2014 The Bridge Crossing Problem
  • 11-26-2014 Magical Squares Game
  • 11-07-2014 QR Decomposition