🛤️

Dijkstra's Algorithm Lecture

Jun 22, 2024

Dijkstra's Algorithm Lecture

Overview

  • Single source shortest path problem
  • Weighted graph
  • Find shortest path from a starting vertex to all other vertices
  • Starting vertex can be any vertex in the graph
  • Minimization problem: optimization problem solved using the greedy method

Greedy Method

  • Solves problems in stages by taking one step and one input at a time
  • Follows predefined procedures to get an optimal solution
  • Dijkstra algorithm follows this approach for finding the minimum result (shortest path)

Dijkstra's Algorithm Procedure

  • Can work on both directed and non-directed graphs
  • Example: Small graph to demonstrate the basic approach

Example

  1. Starting vertex 1, find shortest path to vertices 2 and 3
  2. Direct path to 2 (cost = 2); no direct path to 3 (initially infinity)
  3. Select shortest path to 2 and update shortest path to other vertices (relaxation)
  4. If distance of a vertex + cost of an edge is less than current distance to another vertex, update the distance

Relaxation

  • Check if the distance of vertex u + cost of edge (u, v) < distance of vertex v
  • If true, update the distance of vertex v
  • Repeat steps for relax vertices until shortest paths are determined

Larger Example

  1. Select source vertex and label initial distances
  2. Select and process vertices in order of increasing distance
  3. Perform relaxation to update distances
  4. Continue until shortest paths are found for all vertices

Time Complexity Analysis

  • Finds shortest path to all vertices (n vertices)
  • Relaxes vertices based on connections (E edges)
  • Worst-case time complexity: O(n^2) or Θ(V^2), where n is number of vertices

Negative Weight Edges

  • Dijkstra assumes no negative weight edges
  • Negative edges can occur in real-world problems represented by graphs
  • If negative edge exists, Dijkstra may produce incorrect results

Example with Negative Weight Edge

  1. Original graph with negative weight edge works fine
  2. Modified graph with smaller negative weight edge shows Dijkstra's limitation
  3. Dijkstra fails to provide the correct answer when negative weights are present

Conclusion

  • Dijkstra's algorithm: Greedy approach for single source shortest path
  • Fails with negative weight edges
  • Alternative: Bellman-Ford algorithm to handle negative weights (covered in dynamic programming)

Next Steps

  • Next video: Dynamic programming and the Bellman-Ford algorithm

Full transcript