lessons/week_12/dijsktra_min_heap.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Dijkstra's Algorithm - without paths\n",
        "\n",
        "You're given an integer `start` and a list `edges` of pairs of integers.\n",
        "\n",
        "The list is what's called an adjacency list, and it represents a graph. The number of vertices in the graph is equal to the length of `edges`, where each index `i` in `edges` contains vertex `i`'s outbound edges, in no particular order. Each individual edge is represented by a pair of two numbers, `[destination, distance]`, where the destination is a positive integer denoting the destination vertex and the distance is a positive integer representing the length of the edge (the distance from vertex `i` to vertex `destination`). Note that these edges are directed, meaning that you can only travel from a particular vertex to its destination—not the other way around (unless the destination vertex itself has an outbound edge to the original vertex).\n",
        "\n",
        "Write a function that computes the lengths of the shortest paths between `start` and all of the other vertices in the graph using Dijkstra's algorithm and returns them in an array. Each index `i` in the output array should represent the length of the shortest path between `start` and vertex `i`. If no path is found from `start` to vertex `i`, then `output[i]` should be `-1`.\n",
        "\n",
        "Note that the graph represented by `edges` won't contain any self-loops (vertices that have an outbound edge to themselves) and will only have positively weighted edges (i.e., no negative distances).\n",
        "\n",
        "If you're unfamiliar with Dijkstra's algorithm, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code."
      ],
      "metadata": {
        "id": "mY4jasRMsau5"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Sample Input**"
      ],
      "metadata": {
        "id": "npq7VCLuslOh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "start = 0\n",
        "edges = [\n",
        "    [[1, 7]],\n",
        "    [[2, 6], [3, 20], [4, 3]],\n",
        "    [[3, 14]],\n",
        "    [[4, 2]],\n",
        "    [],\n",
        "    [],\n",
        "]"
      ],
      "metadata": {
        "id": "kWHKqd4Jsd4E"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Sample Output**"
      ],
      "metadata": {
        "id": "VXm2gf_Nso6t"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "[0, 7, 13, 27, 10, -1]"
      ],
      "metadata": {
        "id": "MCawXcPustON",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d0e2371f-950c-4d8e-cee6-fd392fc05350"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0, 7, 13, 27, 10, -1]"
            ]
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Hints\n",
        "\n",
        "Hint 1\n",
        "\n",
        "Dijkstra's algorithm works by visiting vertices in the graph, one by one, all the while keeping track of the current shortest distances from the start vertex to all other vertices and continuously updating these shortest distances. More specifically, the algorithm keeps track of unvisited vertices and visits the unvisited vertex with the shortest distance at any point in time, naturally starting with the start vertex. Whenever the algorithm visits an unvisited vertex, it looks at all of its outbound edges and tries to update the shortest distances from the start to the destinations in the edges, using the current shortest distance to the current vertex as a base. Once the algorithm has visited all of the vertices and considered all of their edges, it is guaranteed to have found the shortest path to each vertex. How can you implement this algorithm?\n",
        "\n",
        "Hint 2\n",
        "\n",
        "The most challenging part of Dijkstra's algorithm is determining how to efficiently find the vertex with the current shortest distance. Can you think of a data structure that could be used to keep track of the distances and to efficiently retrieve the vertex with the current shortest distance at each step?\n",
        "\n",
        "Hint 3\n",
        "\n",
        "Create an array that can store the final shortest distances between the start vertex and all other vertices, as well as a min-heap that will hold all of the unvisited vertices and their current shortest distances. For both the final distances array and the min-heap, initialize all vertices except for the start node as having a distance of infinity; the start node will have a distance 0. Next, write a while loop that will run until the min-heap is empty. At every iteration in the loop, remove the vertex from the top of the heap (the vertex with the shortest distance), loop through all of its edges, and for each edge, update the shortest distance of the destination vertex to be the minimum of the destination's current shortest distance and the currently visited vertex's distance plus the current edge's weight. Once the heap is empty, all of the vertices will have been visited, and you'll have the shortest distances to all vertices stored in your distances array."
      ],
      "metadata": {
        "id": "LoYAnGevsz2r"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class MinHeap:\n",
        "    \"\"\"\n",
        "    MinHeap class: Implements a MinHeap data structure to efficiently manage vertices and their distances\n",
        "    for algorithms like Dijkstra. This implementation keeps track of the position of each vertex using\n",
        "    a vertex map for constant-time lookups and updates.\n",
        "    \"\"\"\n",
        "    def __init__(self, array):\n",
        "        \"\"\"\n",
        "        Initializes the MinHeap with an input array of (vertex, distance) pairs.\n",
        "\n",
        "        Args:\n",
        "            array (list): List of tuples where each tuple is (vertex, distance).\n",
        "                          The distance is typically initialized to infinity except for the starting vertex.\n",
        "\n",
        "        Attributes:\n",
        "            vertexMap (dict): Maps each vertex to its position in the heap for quick access.\n",
        "            heap (list): List representing the binary heap as an array.\n",
        "        \"\"\"\n",
        "        # Create a vertex map: Maps vertices to their indices in the heap.\n",
        "        self.vertexMap = {idx: idx for idx in range(len(array))}\n",
        "\n",
        "        # Build the heap from the input array to satisfy the heap property.\n",
        "        self.heap = self.buildHeap(array)\n",
        "\n",
        "    def isEmpty(self):\n",
        "        \"\"\"\n",
        "        Checks if the heap is empty.\n",
        "\n",
        "        Returns:\n",
        "            bool: True if the heap is empty, False otherwise.\n",
        "        \"\"\"\n",
        "        return len(self.heap) == 0\n",
        "\n",
        "    def buildHeap(self, array):\n",
        "        \"\"\"\n",
        "        Builds the heap from an input array in O(n) time.\n",
        "\n",
        "        Args:\n",
        "            array (list): List of (vertex, distance) pairs.\n",
        "\n",
        "        Returns:\n",
        "            list: The input array transformed into a valid MinHeap.\n",
        "        \"\"\"\n",
        "        # Start from the first parent node and sift down each node.\n",
        "        firstParentIdx = (len(array) - 2) // 2\n",
        "        for currentIdx in reversed(range(firstParentIdx + 1)):\n",
        "            self.siftDown(currentIdx, len(array) - 1, array)\n",
        "        return array\n",
        "\n",
        "    def siftDown(self, currentIdx, endIdx, heap):\n",
        "        \"\"\"\n",
        "        Restores the heap property by \"sifting down\" a node into its correct position.\n",
        "\n",
        "        Args:\n",
        "            currentIdx (int): Index of the node to sift down.\n",
        "            endIdx (int): Last index in the heap.\n",
        "            heap (list): The heap array.\n",
        "\n",
        "        Complexity:\n",
        "            Time: O(log(n))\n",
        "            Space: O(1)\n",
        "        \"\"\"\n",
        "        childOneIdx = currentIdx * 2 + 1  # Index of the first child\n",
        "        while childOneIdx <= endIdx:\n",
        "            # Determine the index of the second child\n",
        "            childTwoIdx = currentIdx * 2 + 2 if currentIdx * 2 + 2 <= endIdx else -1\n",
        "\n",
        "            # Choose the smaller child to maintain the min-heap property\n",
        "            if childTwoIdx != -1 and heap[childTwoIdx][1] < heap[childOneIdx][1]:\n",
        "                idxToSwap = childTwoIdx\n",
        "            else:\n",
        "                idxToSwap = childOneIdx\n",
        "\n",
        "            # Swap if the child is smaller than the current node\n",
        "            if heap[idxToSwap][1] < heap[currentIdx][1]:\n",
        "                self.swap(currentIdx, idxToSwap, heap)\n",
        "                currentIdx = idxToSwap  # Move to the swapped position\n",
        "                childOneIdx = currentIdx * 2 + 1  # Update the first child index\n",
        "            else:\n",
        "                return\n",
        "\n",
        "    def siftUp(self, currentIdx, heap):\n",
        "        \"\"\"\n",
        "        Restores the heap property by \"sifting up\" a node into its correct position.\n",
        "\n",
        "        Args:\n",
        "            currentIdx (int): Index of the node to sift up.\n",
        "            heap (list): The heap array.\n",
        "\n",
        "        Complexity:\n",
        "            Time: O(log(n))\n",
        "            Space: O(1)\n",
        "        \"\"\"\n",
        "        parentIdx = (currentIdx - 1) // 2  # Calculate parent index\n",
        "        while currentIdx > 0 and heap[currentIdx][1] < heap[parentIdx][1]:\n",
        "            self.swap(currentIdx, parentIdx, heap)  # Swap with parent\n",
        "            currentIdx = parentIdx  # Move to the parent's position\n",
        "            parentIdx = (currentIdx - 1) // 2\n",
        "\n",
        "    def remove(self):\n",
        "        \"\"\"\n",
        "        Removes and returns the smallest element (root) in the heap.\n",
        "\n",
        "        Returns:\n",
        "            tuple: The (vertex, distance) pair with the smallest distance.\n",
        "\n",
        "        Complexity:\n",
        "            Time: O(log(n))\n",
        "            Space: O(1)\n",
        "        \"\"\"\n",
        "        if self.isEmpty():\n",
        "            return None\n",
        "\n",
        "        # Swap the root with the last element and remove it\n",
        "        self.swap(0, len(self.heap) - 1, self.heap)\n",
        "        vertex, distance = self.heap.pop()\n",
        "        self.vertexMap.pop(vertex)  # Remove the vertex from the map\n",
        "\n",
        "        # Restore the heap property\n",
        "        self.siftDown(0, len(self.heap) - 1, self.heap)\n",
        "        return vertex, distance\n",
        "\n",
        "    def swap(self, i, j, heap):\n",
        "        \"\"\"\n",
        "        Swaps two nodes in the heap and updates their positions in the vertexMap.\n",
        "\n",
        "        Args:\n",
        "            i (int): Index of the first node.\n",
        "            j (int): Index of the second node.\n",
        "            heap (list): The heap array.\n",
        "        \"\"\"\n",
        "        self.vertexMap[heap[i][0]] = j  # Update vertexMap for heap[i]\n",
        "        self.vertexMap[heap[j][0]] = i  # Update vertexMap for heap[j]\n",
        "        heap[i], heap[j] = heap[j], heap[i]  # Swap the nodes in the heap\n",
        "\n",
        "    def update(self, vertex, value):\n",
        "        \"\"\"\n",
        "        Updates the distance of a given vertex and restores the heap property.\n",
        "\n",
        "        Args:\n",
        "            vertex (int): The vertex whose distance is to be updated.\n",
        "            value (int): The new distance value.\n",
        "\n",
        "        Complexity:\n",
        "            Time: O(log(n))\n",
        "            Space: O(1)\n",
        "        \"\"\"\n",
        "        # Update the heap with the new (vertex, value) pair\n",
        "        self.heap[self.vertexMap[vertex]] = (vertex, value)\n",
        "        # Restore the heap property by sifting up the updated node\n",
        "        self.siftUp(self.vertexMap[vertex], self.heap)"
      ],
      "metadata": {
        "id": "vDjqHyFXN1zj"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# O((v + e) * log(v)) time | O(v) space — where v is the number\n",
        "# of vertices and e is the number of edges in the input graph\n",
        "def dijkstrasAlgorithm(start, edges):\n",
        "    \"\"\"\n",
        "    Implements Dijkstra's algorithm to find the shortest paths from a starting vertex to all other vertices\n",
        "    in a weighted graph. The graph is represented using an adjacency list.\n",
        "\n",
        "    Args:\n",
        "        start (int): The starting vertex index.\n",
        "        edges (list of list): An adjacency list where each index represents a vertex, and each entry\n",
        "                              is a list of [destination, weight] pairs.\n",
        "\n",
        "    Returns:\n",
        "        list: A list of minimum distances from the starting vertex to each vertex in the graph.\n",
        "              If a vertex is unreachable, its distance is represented as -1.\n",
        "    \"\"\"\n",
        "    # Step 1: Initialize the number of vertices in the graph\n",
        "    numberOfVertices = len(edges)\n",
        "\n",
        "    # Step 2: Initialize the minimum distances with infinity\n",
        "    # Set the starting vertex's distance to 0\n",
        "    minDistances = [float(\"inf\") for _ in range(numberOfVertices)]\n",
        "    minDistances[start] = 0\n",
        "\n",
        "    # Step 3: Initialize the MinHeap to track the vertices and their current shortest distances\n",
        "    minDistancesHeap = MinHeap([(idx, float(\"inf\")) for idx in range(numberOfVertices)])\n",
        "    minDistancesHeap.update(start, 0)  # Update the starting vertex's distance to 0\n",
        "\n",
        "    # Step 4: Process vertices until the heap is empty\n",
        "    while not minDistancesHeap.isEmpty():\n",
        "        # Extract the vertex with the smallest known distance\n",
        "        vertex, currentMinDistance = minDistancesHeap.remove()\n",
        "\n",
        "        # If the current distance is infinity, no further reachable vertices exist\n",
        "        if currentMinDistance == float(\"inf\"):\n",
        "            break\n",
        "\n",
        "        # Step 5: Relaxation - Update distances for all neighboring vertices\n",
        "        for edge in edges[vertex]:\n",
        "            destination, distanceToDestination = edge  # Extract neighbor and weight\n",
        "\n",
        "            # Calculate the new potential path distance\n",
        "            newPathDistance = currentMinDistance + distanceToDestination\n",
        "            currentDestinationDistance = minDistances[destination]\n",
        "\n",
        "            # If the new path is shorter, update the distance and the heap\n",
        "            if newPathDistance < currentDestinationDistance:\n",
        "                minDistances[destination] = newPathDistance\n",
        "                minDistancesHeap.update(destination, newPathDistance)\n",
        "\n",
        "    # Step 6: Convert unreachable vertices' distances from infinity to -1\n",
        "    return list(map(lambda x: -1 if x == float(\"inf\") else x, minDistances))"
      ],
      "metadata": {
        "id": "g-jMjCkDs0Kx"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def test_dijkstras_algorithm():\n",
        "    \"\"\"\n",
        "    Test function for Dijkstra's algorithm.\n",
        "\n",
        "    This test evaluates the correctness of the `dijkstrasAlgorithm` function using a predefined input graph\n",
        "    and expected output. The graph is represented as an adjacency list, and the test ensures that the\n",
        "    algorithm computes the shortest paths correctly.\n",
        "\n",
        "    Input Graph:\n",
        "        Node 0 -> Node 1 (weight 7)\n",
        "        Node 1 -> Node 2 (weight 6), Node 3 (weight 20), Node 4 (weight 3)\n",
        "        Node 2 -> Node 3 (weight 14)\n",
        "        Node 3 -> Node 4 (weight 2)\n",
        "        Node 4 -> No outgoing edges\n",
        "        Node 5 -> No outgoing edges\n",
        "\n",
        "    Expected Output:\n",
        "        [0, 7, 13, 27, 10, -1]\n",
        "        - Shortest distances from node 0 to all other nodes.\n",
        "        - `-1` represents unreachable nodes (node 5 in this case).\n",
        "\n",
        "    Assertions:\n",
        "        The test checks if the result matches the expected output and raises an assertion error otherwise.\n",
        "\n",
        "    Returns:\n",
        "        None. Prints \"Test passed\" if the output is correct.\n",
        "    \"\"\"\n",
        "    # Input graph represented as an adjacency list\n",
        "    edges = [\n",
        "        [[1, 7]],                   # Node 0 -> Node 1 (weight 7)\n",
        "        [[2, 6], [3, 20], [4, 3]],  # Node 1 -> Node 2 (6), Node 3 (20), Node 4 (3)\n",
        "        [[3, 14]],                  # Node 2 -> Node 3 (weight 14)\n",
        "        [[4, 2]],                   # Node 3 -> Node 4 (weight 2)\n",
        "        [],                         # Node 4 has no outgoing edges\n",
        "        []                          # Node 5 has no outgoing edges\n",
        "    ]\n",
        "    start = 0  # Starting node for Dijkstra's algorithm\n",
        "\n",
        "    # Expected output: Shortest distances from the starting node\n",
        "    expected_output = [0, 7, 13, 27, 10, -1]\n",
        "\n",
        "    # Step 1: Run Dijkstra's algorithm on the input graph\n",
        "    result = dijkstrasAlgorithm(start, edges)\n",
        "\n",
        "    # Step 2: Compare the result with the expected output\n",
        "    assert result == expected_output, f\"Test failed: expected {expected_output}, but got {result}\"\n",
        "\n",
        "    # Step 3: If no assertion error, print test success message\n",
        "    print(\"Test passed: Output matches expected result.\")\n",
        "\n",
        "\n",
        "# Run the test function\n",
        "test_dijkstras_algorithm()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MQUBh2xfxcQt",
        "outputId": "cd75528f-0d2e-4846-9940-f8f88583f2e7"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Test passed: Output matches expected result.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Dijstrak's Algorithm with Path"
      ],
      "metadata": {
        "id": "Bt4vSnf8yKpA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def dijkstrasAlgorithmWithPaths(start, edges):\n",
        "    \"\"\"\n",
        "    Implements Dijkstra's algorithm to compute the shortest paths from a starting vertex to all other vertices\n",
        "    in a weighted graph. It also tracks the predecessors of each vertex for path reconstruction.\n",
        "\n",
        "    Args:\n",
        "        start (int): The index of the starting vertex.\n",
        "        edges (list of list): Adjacency list representation of the graph, where each index represents a vertex,\n",
        "                              and each entry is a list of [destination, weight] pairs.\n",
        "\n",
        "    Returns:\n",
        "        tuple: A tuple containing:\n",
        "            - minDistances (list): A list of the shortest distances from the starting vertex to each vertex.\n",
        "                                   Vertices that are unreachable will have a distance of `float(\"inf\")`.\n",
        "            - previousNodes (list): A list where each index points to the predecessor of the vertex\n",
        "                                    in the shortest path. If no path exists, the predecessor is `None`.\n",
        "\n",
        "    Algorithm Steps:\n",
        "        1. Initialize distances with `infinity` and set the starting vertex distance to 0.\n",
        "        2. Use a MinHeap to manage and efficiently retrieve the vertex with the smallest known distance.\n",
        "        3. For each vertex, relax its edges to update distances to neighboring vertices.\n",
        "        4. Track the predecessor of each vertex to allow path reconstruction later.\n",
        "        5. Return the minimum distances and the list of predecessors.\n",
        "    \"\"\"\n",
        "    numberOfVertices = len(edges)  # Total number of vertices in the graph\n",
        "\n",
        "    # Step 1: Initialize minimum distances and predecessors\n",
        "    minDistances = [float(\"inf\")] * numberOfVertices  # All distances set to infinity initially\n",
        "    minDistances[start] = 0  # Distance to the start node is 0\n",
        "\n",
        "    previousNodes = [None] * numberOfVertices  # Array to store the predecessor of each vertex\n",
        "\n",
        "    # Step 2: Initialize the MinHeap\n",
        "    heap = MinHeap([(i, float(\"inf\")) for i in range(numberOfVertices)])\n",
        "    heap.update(start, 0)  # Update the distance of the starting vertex to 0\n",
        "\n",
        "    # Step 3: Process vertices until the heap is empty\n",
        "    while not heap.isEmpty():\n",
        "        # Extract the vertex with the smallest known distance\n",
        "        vertex, currentMinDistance = heap.remove()\n",
        "\n",
        "        # Ignore outdated distances (e.g., if a shorter distance was already found)\n",
        "        if currentMinDistance > minDistances[vertex]:\n",
        "            continue\n",
        "\n",
        "        # Step 4: Relaxation - Update distances to neighboring vertices\n",
        "        for edge in edges[vertex]:\n",
        "            destination, weight = edge  # Extract destination vertex and edge weight\n",
        "\n",
        "            # Calculate the new potential distance to the destination vertex\n",
        "            newPathDistance = currentMinDistance + weight\n",
        "\n",
        "            # Update if the new path is shorter\n",
        "            if newPathDistance <= minDistances[destination]:\n",
        "                minDistances[destination] = newPathDistance\n",
        "                previousNodes[destination] = vertex  # Track the predecessor for path reconstruction\n",
        "                heap.update(destination, newPathDistance)  # Update the heap with the new distance\n",
        "\n",
        "    return minDistances, previousNodes"
      ],
      "metadata": {
        "id": "Adzk8NFmVUXu"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def reconstructPath(previousNodes, start, end):\n",
        "    \"\"\"\n",
        "    Reconstructs the shortest path from the start node to the end node using the predecessor list.\n",
        "\n",
        "    Args:\n",
        "        previousNodes (list): A list where each index corresponds to a node, and the value at that index\n",
        "                              is the predecessor node in the shortest path. `None` indicates no predecessor.\n",
        "        start (int): The starting node index.\n",
        "        end (int): The destination node index.\n",
        "\n",
        "    Returns:\n",
        "        list: A list of nodes representing the shortest path from the start node to the end node.\n",
        "              If no path exists, returns an empty list.\n",
        "\n",
        "    Algorithm:\n",
        "        1. Start from the destination node (`end`) and trace back to the start node (`start`) using\n",
        "           the `previousNodes` list.\n",
        "        2. Append each node encountered to the `path` list.\n",
        "        3. Reverse the `path` list to produce the correct order from start to end.\n",
        "        4. If no valid path exists (e.g., disconnected graph), return an empty list.\n",
        "\n",
        "    Example:\n",
        "        previousNodes = [None, 0, 1, 2]  # Predecessor list\n",
        "        start = 0\n",
        "        end = 3\n",
        "        reconstructPath(previousNodes, start, end) -> [0, 1, 2, 3]\n",
        "    \"\"\"\n",
        "    path = []  # Initialize an empty list to store the path\n",
        "    currentNode = end  # Start tracing from the destination node\n",
        "\n",
        "    # Step 1: Trace back from the destination node to the start node\n",
        "    while currentNode is not None and currentNode != start:\n",
        "        path.append(currentNode)  # Add the current node to the path\n",
        "        currentNode = previousNodes[currentNode]  # Move to the predecessor node\n",
        "\n",
        "    # Step 2: Add the start node if a valid path was found\n",
        "    if currentNode == start:\n",
        "        path.append(start)  # Add the start node to the path\n",
        "        path.reverse()  # Reverse the path to get the correct order from start to end\n",
        "        return path\n",
        "\n",
        "    # Step 3: If no path exists, return an empty list\n",
        "    return []"
      ],
      "metadata": {
        "id": "f7zCuZd5QC9H"
      },
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def test_dijkstrasAlgorithmWithPaths():\n",
        "    \"\"\"\n",
        "    Test function for the `dijkstrasAlgorithmWithPaths` function.\n",
        "\n",
        "    This test verifies:\n",
        "        1. The correctness of the minimum distances calculated by Dijkstra's algorithm.\n",
        "        2. The correctness of the reconstructed paths using the `reconstructPath` function.\n",
        "\n",
        "    Input Graph (Adjacency List):\n",
        "        - Node 0 -> Node 1 (weight 7)\n",
        "        - Node 1 -> Node 2 (weight 6), Node 3 (weight 20), Node 4 (weight 3)\n",
        "        - Node 2 -> Node 3 (weight 14)\n",
        "        - Node 3 -> Node 4 (weight 2)\n",
        "        - Node 4 has no outgoing edges\n",
        "        - Node 5 is isolated (no incoming or outgoing edges).\n",
        "\n",
        "    Expected Results:\n",
        "        - Minimum Distances:\n",
        "            [0, 7, 13, 27, 10, float(\"inf\")]\n",
        "            - Distances from node 0 to all other nodes. `float(\"inf\")` represents unreachable nodes.\n",
        "        - Reconstructed Paths:\n",
        "            - Path to node 3: [0, 1, 2, 3]\n",
        "            - Path to node 4: [0, 1, 4]\n",
        "            - Path to node 5: []\n",
        "\n",
        "    Assertions:\n",
        "        The test uses assertions to ensure that the computed distances and paths match the expected values.\n",
        "\n",
        "    Returns:\n",
        "        None. Prints \"All tests passed!\" if the results are correct.\n",
        "    \"\"\"\n",
        "    # Step 1: Define the input graph as an adjacency list\n",
        "    edges = [\n",
        "        [[1, 7]],                   # Node 0 -> Node 1 (weight 7)\n",
        "        [[2, 6], [3, 20], [4, 3]],  # Node 1 -> Node 2 (6), Node 3 (20), Node 4 (3)\n",
        "        [[3, 14]],                  # Node 2 -> Node 3 (weight 14)\n",
        "        [[4, 2]],                   # Node 3 -> Node 4 (weight 2)\n",
        "        [],                         # Node 4 has no outgoing edges\n",
        "        []                          # Node 5 has no outgoing edges\n",
        "    ]\n",
        "    start = 0  # Starting node for Dijkstra's algorithm\n",
        "\n",
        "    # Step 2: Run Dijkstra's algorithm\n",
        "    minDistances, previousNodes = dijkstrasAlgorithmWithPaths(start, edges)\n",
        "\n",
        "    # Step 3: Check the minimum distances\n",
        "    expectedDistances = [0, 7, 13, 27, 10, float(\"inf\")]\n",
        "    assert minDistances == expectedDistances, f\"Distances test failed: {minDistances}\"\n",
        "\n",
        "    # Step 4: Reconstruct paths to specific nodes and validate them\n",
        "    # Path to node 3\n",
        "    path_to_3 = reconstructPath(previousNodes, start, 3)\n",
        "    expectedPathTo3 = [0, 1, 2, 3]\n",
        "    assert path_to_3 == expectedPathTo3, f\"Path to 3 test failed: {path_to_3}\"\n",
        "\n",
        "    # Path to node 4\n",
        "    path_to_4 = reconstructPath(previousNodes, start, 4)\n",
        "    expectedPathTo4 = [0, 1, 4]\n",
        "    assert path_to_4 == expectedPathTo4, f\"Path to 4 test failed: {path_to_4}\"\n",
        "\n",
        "    # Path to node 5 (unreachable)\n",
        "    path_to_5 = reconstructPath(previousNodes, start, 5)\n",
        "    expectedPathTo5 = []\n",
        "    assert path_to_5 == expectedPathTo5, f\"Path to 5 test failed: {path_to_5}\"\n",
        "\n",
        "    # Step 5: Print success message if all tests pass\n",
        "    print(\"All tests passed!\")\n",
        "\n",
        "\n",
        "# Run the test\n",
        "test_dijkstrasAlgorithmWithPaths()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5mMLPzmnVWHM",
        "outputId": "e6858260-23c5-435f-a0f1-68d465cea832"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "All tests passed!\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "lFdlmgKpRrfQ"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}