Now it’s time to become a pathfinding god.
Enter the realm of Shortest Path Algorithms, where we stop wandering and start optimizing.

Because getting from Point A to Point B isn’t enough — we want the fastest, cheapest, or most efficient way there.
And in the world of graphs, that means whipping out some algorithmic wizardry like Dijkstra’s Algorithm and friends.

---

Shortest Path Algorithms: Because Ain’t Nobody Got Time for Long Routes

"Sure, your code works… but why is your algorithm taking the scenic route through 5 extra nodes and a metaphorical snowstorm?"
— USask TA grading your CMPT 280 assignment

---

🧭 What’s a Shortest Path Algorithm?

A shortest path algorithm finds the most optimal route between two nodes in a graph based on some cost or weight — like distance, time, or sadness.

This isn’t just “get there.”
This is “get there efficiently.”

---

🛣️ Real-World Examples

• 🚍 Google Maps finding the fastest bus route from Louis’ Pub to your 8am in Engineering

• 🧠 AI pathfinding in games (think: “How does this NPC know where to walk?”)

• 📦 Logistics and delivery optimization (Amazon-level route planning)

• 🤝 Social networks: shortest chain between two users

---

📚 Algorithms You Need to Know

We’re focusing on Dijkstra’s Algorithm, but let’s set the stage:

---

🔥 Dijkstra’s Algorithm: The Java Superstar

“I’m not the fastest, but I’m the most dependable friend in your algorithm circle.”

🎯 What It Solves:

Finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights.

🧠 How It Works (High Level):

1. Start at the source node

2. Set all distances to ∞ (except source = 0)

3. Use a priority queue (min-heap) to pick the next “closest” node

4. Update the shortest paths to neighbors

5. Repeat until all nodes are processed

---

🧪 Java Code (Simplified Example)

java
CopyEdit
class Node {
    String name;
    int distance;

    public Node(String name, int distance) {
        this.name = name;
        this.distance = distance;
    }
}

public Map<String, Integer> dijkstra(Map<String, List<Node>> graph, String start) {
    Map<String, Integer> distances = new HashMap<>();
    for (String node : graph.keySet()) {
        distances.put(node, Integer.MAX_VALUE);
    }
    distances.put(start, 0);

    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
    pq.add(new Node(start, 0));

    while (!pq.isEmpty()) {
        Node current = pq.poll();

        for (Node neighbor : graph.get(current.name)) {
            int newDist = distances.get(current.name) + neighbor.distance;
            if (newDist < distances.get(neighbor.name)) {
                distances.put(neighbor.name, newDist);
                pq.add(new Node(neighbor.name, newDist));
            }
        }
    }

    return distances;
}

✨ Outputs a map of shortest distances from start to every other node.

---

🧭 How Dijkstra’s Chooses the “Next Best” Node

“Always pick the closest unvisited node.”

It’s like being in the Bowl and deciding where to walk next by which building is nearest — but with logic instead of vibes.

That’s why we use a priority queue — to always grab the most promising next step.

---

❗ Why Dijkstra’s Needs Positive Weights

Dijkstra’s assumes once you find a shorter path, it stays shorter.

If you suddenly throw in a negative edge, it might discover a cheaper path after it already processed a node — and it won’t go back.

It’s the "one and done" friend. Once a node is marked as visited? It’s history.

---

💡 Use Cases

✅ Great For:

• Shortest routes in maps or networks

• Routing protocols (e.g., OSPF in networking)

• Game AI navigation

• Project planning (e.g., earliest task completion)

❌ Not Great For:

• Graphs with negative weights

• Scenarios requiring all-pairs shortest paths (Floyd-Warshall is better)

---

📦 Visual Example

Imagine this graph:

css
CopyEdit
    A
   / \
  1   4
 B-----C
   2

Dijkstra from A:

• A → B = 1

• A → C = 4

• B → C = 1 + 2 = 3 (cheaper than 4)

Dijkstra will pick the cheapest in total — not just the direct edge.

---

🧠 How It Fits in Regression Testing

If you’re testing a method that finds shortest paths, you better:

• ✅ Write test cases for multiple paths

• ✅ Check for correct weights, not just paths

• ✅ Handle disconnected nodes

• ✅ Confirm no regression after optimization (i.e., your "new fast version" doesn't break it)

---

🧪 Test Case Best Practices for Dijkstra

• Basic case: Linear graph with increasing weights

• Complex case: Multiple equal-weight paths

• Edge case: Disconnected graph

• Negative case: No negative weights (but test for error handling)

---

🔍 BFS as a Special Case

If your graph is unweighted, BFS becomes a shortest path algorithm!
Because all edges have equal cost, level-order traversal finds the shortest path.

That’s why BFS is often used in:

• Mazes

• Social graphs

• Puzzles

But when you add weights? BFS can’t help you anymore.
That’s where Dijkstra steps up.

---

🧠 TL;DR (Too Long, Didn’t Pathfind)

• Dijkstra’s Algorithm finds the shortest path from a source to all nodes

• Uses a priority queue

• Works with positive-weighted graphs

• It’s greedy, efficient, and deterministic

• Foundation for tons of real-world systems

• Fails with negative weights (use Bellman-Ford instead)

• Essential in regression testing for path-related functions

---

🎓 Final Words from the Algorithm Highway

Dijkstra’s isn’t just an algorithm — it’s a mindset.

It’s the “don’t waste time wandering” friend.
The “do it right the first time” energy.
The pathfinder who says, “I’ll get there — and I’ll get there well.”

Add it to your toolbox. Understand how it works. And for the love of all that is clean code — test it properly before pushing to prod.