Dijkstra's Algorithm for Finding the Shortest Path

Introduction

• Importance of sleep for students.
• Need for optimizing routes to school to maximize sleep.

Problem

• Classes start at 9 AM, requiring early wake-up.
• Multiple possible routes to school.
• Need to find the shortest route without physically trying each one.

Solution: Dijkstra's Algorithm

• Purpose: Finds the shortest route between two points.
• Benefit: Can be used from the comfort of bed.

How Dijkstra's Algorithm Works

Graph Representation

• Graph Components:
  • Nodes: Represent locations (e.g., home, school).
  • Edges: Represent paths between nodes with a value assigned (time taken to traverse the path).

Steps to Find the Shortest Route

1. Initialization:

   • Choose a start node (Home) and a target node (School).
   • Set the starting node (Home) running value to 0 as it requires no travel.

2. Node Exploration:

   • Select the node with the lowest running value and set it as "visited" (fixed value).
   • Calculate running values for adjacent nodes (time taken from start node to adjacent nodes).

3. Updating Running Values:

   • Explore each node by setting the lowest running value as fixed.
   • Update running values for all unvisited adjacent nodes.
   • Running values are cumulative: Add previous running value to the new edge value (e.g., 2 + 6 = 8).
   • Adjust running values if a lower path is found.

4. Completion:

   • Repeat until the target node (School) has the lowest running value.
   • Shortest path can be found before all nodes are visited.

Conclusion

• Dijkstra's Algorithm helps determine the shortest path efficiently.
• Maximizes students' rest by ensuring the quickest route to school.