Skip to content

Instantly share code, notes, and snippets.

@EssamWisam

EssamWisam/shortest.ipynb

Created April 27, 2025 17:57
Show Gist options
  • Save EssamWisam/58685c246e74bf4bf94cc89ef171adb0 to your computer and use it in GitHub Desktop.
Save EssamWisam/58685c246e74bf4bf94cc89ef171adb0 to your computer and use it in GitHub Desktop.
Download ZIP
Shortest Paths
Display the source blob
Display the rendered blob
Raw
shortest.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 6,
"id": "aea99bab",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Testing Dijkstra's algorithm:\n",
"----------------------------------------\n",
"Node s: Expected=0, Actual=0 - PASS\n",
"Node t: Expected=8, Actual=8 - PASS\n",
"Node x: Expected=9, Actual=9 - PASS\n",
"Node y: Expected=5, Actual=5 - PASS\n",
"Node z: Expected=7, Actual=7 - PASS\n",
"----------------------------------------\n",
"All tests passed! The implementation is correct.\n"
]
}
],
"source": [
"import heapq\n",
"\n",
"def dijkstra(graph, start):\n",
" \"\"\"\n",
" Implements Dijkstra's algorithm to find shortest paths from start node to all other nodes.\n",
" \n",
" Args:\n",
" graph: Dictionary where keys are nodes and values are dictionaries of connected nodes and edge weights\n",
" start: Starting node\n",
" \n",
" Returns:\n",
" distances: Dictionary of shortest distances from start to all nodes\n",
" predecessors: Dictionary of predecessors in the shortest path\n",
" \"\"\"\n",
" # Initialize distances with infinity for all nodes except start\n",
" distances = {node: float('infinity') for node in graph}\n",
" distances[start] = 0\n",
" \n",
" # Initialize predecessors\n",
" predecessors = {node: None for node in graph}\n",
" \n",
" # Priority queue to store vertices to visit\n",
" priority_queue = [(0, start)]\n",
" \n",
" # Keep track of visited nodes\n",
" visited = set()\n",
" \n",
" while priority_queue:\n",
" # Get the node with the smallest distance\n",
" current_distance, current_node = heapq.heappop(priority_queue)\n",
" \n",
" # If we've already processed this node, skip it\n",
" if current_node in visited:\n",
" continue\n",
" \n",
" # Mark node as visited\n",
" visited.add(current_node)\n",
" \n",
" # If current distance is greater than the known distance, skip\n",
" if current_distance > distances[current_node]:\n",
" continue\n",
" \n",
" # Check all neighbors of the current node\n",
" for neighbor, weight in graph[current_node].items():\n",
" # Calculate potential new distance\n",
" distance = current_distance + weight\n",
" \n",
" # If we found a shorter path, update distance and predecessor\n",
" if distance < distances[neighbor]:\n",
" distances[neighbor] = distance\n",
" predecessors[neighbor] = current_node\n",
" heapq.heappush(priority_queue, (distance, neighbor))\n",
" \n",
" return distances, predecessors\n",
"\n",
"\n",
"def test_dijkstra():\n",
" \"\"\"\n",
" Test function to verify Dijkstra's algorithm against expected results.\n",
" \"\"\"\n",
" # Define the graph from the image\n",
" graph = {\n",
" 's': {'t': 10, 'y': 5},\n",
" 't': {'x': 1, 'y': 2},\n",
" 'y': {'t': 3, 'z': 2},\n",
" 'x': {'z': 4},\n",
" 'z': {'x': 6, 's': 7}\n",
" }\n",
" \n",
" # Expected shortest distances from node 's'\n",
" expected_distances = {\n",
" 's': 0,\n",
" 't': 8,\n",
" 'x': 9,\n",
" 'y': 5,\n",
" 'z': 7\n",
" }\n",
" \n",
" # Run Dijkstra's algorithm from node 's'\n",
" start_node = 's'\n",
" actual_distances, predecessors = dijkstra(graph, start_node)\n",
" \n",
" # Verify results\n",
" all_correct = True\n",
" print(\"Testing Dijkstra's algorithm:\")\n",
" print(\"-\" * 40)\n",
" \n",
" for node, expected in expected_distances.items():\n",
" actual = actual_distances[node]\n",
" result = \"PASS\" if actual == expected else \"FAIL\"\n",
" print(f\"Node {node}: Expected={expected}, Actual={actual} - {result}\")\n",
" if actual != expected:\n",
" all_correct = False\n",
" \n",
" print(\"-\" * 40)\n",
" if all_correct:\n",
" print(\"All tests passed! The implementation is correct.\")\n",
" else:\n",
" print(\"Some tests failed. Check the implementation.\")\n",
"\n",
"# Run the test\n",
"if __name__ == \"__main__\":\n",
" test_dijkstra()"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "8b3557e8",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"No negative cycle found: True\n",
"Shortest distances from source vertex 's':\n",
"Vertex s: 0\n",
"Vertex t: 2\n",
"Vertex x: 4\n",
"Vertex y: 7\n",
"Vertex z: -2\n",
"✓ Distance to s is correct: 0\n",
"✓ Distance to t is correct: 2\n",
"✓ Distance to x is correct: 4\n",
"✓ Distance to y is correct: 7\n",
"✓ Distance to z is correct: -2\n",
"\n",
"All shortest distances match the expected values!\n"
]
}
],
"source": [
"def bellman_ford(graph, source):\n",
" # Step 1: Initialize distances from source to all other vertices as INFINITY\n",
" # and distance to source as 0\n",
" distances = {vertex: float('inf') for vertex in graph}\n",
" distances[source] = 0\n",
" \n",
" # Step 2: Relax all edges |V| - 1 times\n",
" # A path can have at most |V| - 1 edges\n",
" for _ in range(len(graph) - 1):\n",
" for u in graph:\n",
" for v, weight in graph[u].items():\n",
" # If edge (u, v) can be relaxed, relax it\n",
" if distances[u] != float('inf') and distances[u] + weight < distances[v]:\n",
" distances[v] = distances[u] + weight\n",
" \n",
" # Step 3: Check for negative-weight cycles\n",
" # If we can relax further, then there is a negative-weight cycle\n",
" for u in graph:\n",
" for v, weight in graph[u].items():\n",
" if distances[u] != float('inf') and distances[u] + weight < distances[v]:\n",
" return False, distances # Negative cycle exists\n",
" \n",
" return True, distances # No negative cycles, return distances\n",
"\n",
"# Test with the graph from the image\n",
"def test_bellman_ford():\n",
" # Create the graph as an adjacency list with all edges and their weights\n",
" graph = {\n",
" 's': {'t': 6, 'y': 7},\n",
" 't': {'x': 5, 'y': 8, 'z': -4},\n",
" 'x': {'t': -2},\n",
" 'y': {'x': -3, 'z': 9},\n",
" 'z': {'s': 2, 'x': 7},\n",
" }\n",
" \n",
" # Add the additional edges from x to z and z to x that weren't initially included\n",
" graph['x']['z'] = -3\n",
" graph['z']['x'] = 7\n",
" \n",
" # Run Bellman-Ford algorithm with source vertex 's'\n",
" no_negative_cycle, distances = bellman_ford(graph, 's')\n",
" \n",
" print(\"No negative cycle found:\", no_negative_cycle)\n",
" print(\"Shortest distances from source vertex 's':\")\n",
" for vertex, distance in sorted(distances.items()):\n",
" print(f\"Vertex {vertex}: {distance}\")\n",
" \n",
" # Verify the expected shortest distances\n",
" expected_distances = {'s': 0, 't': 2, 'x': 4, 'y': 7, 'z': -2}\n",
" for vertex, expected_distance in sorted(expected_distances.items()):\n",
" if distances[vertex] == expected_distance:\n",
" print(f\"✓ Distance to {vertex} is correct: {distances[vertex]}\")\n",
" else:\n",
" print(f\"✗ Distance to {vertex} is incorrect. Expected: {expected_distance}, Got: {distances[vertex]}\")\n",
" \n",
" all_correct = all(distances[v] == expected_distances[v] for v in expected_distances)\n",
" if all_correct:\n",
" print(\"\\nAll shortest distances match the expected values!\")\n",
" else:\n",
" print(\"\\nSome distances don't match the expected values.\")\n",
" \n",
" return distances, expected_distances\n",
"\n",
"# Run the test\n",
"if __name__ == \"__main__\":\n",
" test_bellman_ford()"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "a923c011",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Initial Distance Matrix D(0):\n",
"[0.0, 3.0, 8.0, '∞', -4.0]\n",
"['∞', 0.0, '∞', 1.0, 7.0]\n",
"['∞', 4.0, 0.0, '∞', '∞']\n",
"[2.0, '∞', -5.0, 0.0, '∞']\n",
"['∞', '∞', '∞', 6.0, 0.0]\n",
"\n",
"Initial Predecessor Matrix Pi(0):\n",
"['NIL', 1, 1, 'NIL', 1]\n",
"['NIL', 'NIL', 'NIL', 2, 2]\n",
"['NIL', 3, 'NIL', 'NIL', 'NIL']\n",
"[4, 'NIL', 4, 'NIL', 'NIL']\n",
"['NIL', 'NIL', 'NIL', 5, 'NIL']\n",
"\n",
"Final Distance Matrix D(5):\n",
"[0.0, 1.0, -3.0, 2.0, -4.0]\n",
"[3.0, 0.0, -4.0, 1.0, -1.0]\n",
"[7.0, 4.0, 0.0, 5.0, 3.0]\n",
"[2.0, -1.0, -5.0, 0.0, -2.0]\n",
"[8.0, 5.0, 1.0, 6.0, 0.0]\n",
"\n",
"Final Predecessor Matrix Pi(5):\n",
"['NIL', 3, 4, 5, 1]\n",
"[4, 'NIL', 4, 2, 1]\n",
"[4, 3, 'NIL', 2, 1]\n",
"[4, 3, 4, 'NIL', 1]\n",
"[4, 3, 4, 5, 'NIL']\n",
"\n",
"Expected D(5) from example:\n",
"[ 0 1 -3 2 -4]\n",
"[ 3 0 -4 1 -1]\n",
"[7 4 0 5 3]\n",
"[ 2 -1 -5 0 -2]\n",
"[8 5 1 6 0]\n",
"\n",
"Expected Pi(5) from example:\n",
"['NIL', 3, 4, 5, 1]\n",
"[4, 'NIL', 4, 2, 1]\n",
"[4, 3, 'NIL', 2, 1]\n",
"[4, 3, 4, 'NIL', 1]\n",
"[4, 3, 4, 5, 'NIL']\n",
"\n",
"Do our D(5) and the expected D(5) match? True\n",
"Do our Pi(5) and the expected Pi(5) match? True\n"
]
}
],
"source": [
"import numpy as np\n",
"\n",
"def floyd_warshall_algorithm(graph):\n",
" n = len(graph)\n",
" \n",
" # Initialize distance and predecessor matrices\n",
" D = [graph.copy()]\n",
" \n",
" # Create initial predecessor matrix\n",
" # Using None to represent NIL during calculations\n",
" Pi = [[None for _ in range(n)] for _ in range(n)]\n",
" \n",
" # Using the values from Pi(0) in the example\n",
" Pi[0][1] = 1\n",
" Pi[0][2] = 1\n",
" Pi[0][4] = 1\n",
" Pi[1][3] = 2\n",
" Pi[1][4] = 2\n",
" Pi[2][1] = 3\n",
" Pi[3][0] = 4\n",
" Pi[3][2] = 4\n",
" Pi[4][3] = 5\n",
" \n",
" # Store initial Pi matrix\n",
" Pi_matrices = [np.array(Pi, dtype=object)]\n",
" \n",
" # Main Floyd-Warshall algorithm\n",
" for k in range(n):\n",
" # Create new distance matrix for this iteration\n",
" current_D = D[k].copy()\n",
" current_Pi = Pi_matrices[k].copy()\n",
" \n",
" for i in range(n):\n",
" for j in range(n):\n",
" if current_D[i][k] != float('inf') and current_D[k][j] != float('inf'):\n",
" if current_D[i][j] > current_D[i][k] + current_D[k][j]:\n",
" current_D[i][j] = current_D[i][k] + current_D[k][j]\n",
" current_Pi[i][j] = current_Pi[k][j]\n",
" \n",
" D.append(current_D)\n",
" Pi_matrices.append(current_Pi)\n",
" \n",
" return D, Pi_matrices\n",
"\n",
"# Initial distance matrix D(0) from the example\n",
"D0 = np.array([\n",
" [0, 3, 8, float('inf'), -4],\n",
" [float('inf'), 0, float('inf'), 1, 7],\n",
" [float('inf'), 4, 0, float('inf'), float('inf')],\n",
" [2, float('inf'), -5, 0, float('inf')],\n",
" [float('inf'), float('inf'), float('inf'), 6, 0]\n",
"])\n",
"\n",
"# Run the algorithm\n",
"D_matrices, Pi_matrices = floyd_warshall_algorithm(D0)\n",
"\n",
"# Print initial and final matrices\n",
"print(\"Initial Distance Matrix D(0):\")\n",
"for row in D_matrices[0]:\n",
" print([x if x != float('inf') else \"∞\" for x in row])\n",
"\n",
"print(\"\\nInitial Predecessor Matrix Pi(0):\")\n",
"for row in Pi_matrices[0]:\n",
" print([\"NIL\" if x is None else x for x in row])\n",
"\n",
"print(\"\\nFinal Distance Matrix D(5):\")\n",
"for row in D_matrices[5]:\n",
" print([x if x != float('inf') else \"∞\" for x in row])\n",
"\n",
"print(\"\\nFinal Predecessor Matrix Pi(5):\")\n",
"for row in Pi_matrices[5]:\n",
" print([\"NIL\" if x is None else x for x in row])\n",
"\n",
"# Expected matrices from the example\n",
"D5_expected = np.array([\n",
" [0, 1, -3, 2, -4],\n",
" [3, 0, -4, 1, -1],\n",
" [7, 4, 0, 5, 3],\n",
" [2, -1, -5, 0, -2],\n",
" [8, 5, 1, 6, 0]\n",
"])\n",
"\n",
"Pi5_expected = [\n",
" [None, 3, 4, 5, 1],\n",
" [4, None, 4, 2, 1],\n",
" [4, 3, None, 2, 1],\n",
" [4, 3, 4, None, 1],\n",
" [4, 3, 4, 5, None]\n",
"]\n",
"\n",
"print(\"\\nExpected D(5) from example:\")\n",
"for row in D5_expected:\n",
" print(row)\n",
"\n",
"print(\"\\nExpected Pi(5) from example:\")\n",
"for row in Pi5_expected:\n",
" print([\"NIL\" if x is None else x for x in row])\n",
"\n",
"# Check if our final matrices match the expected ones\n",
"D_matches = np.array_equal(D_matrices[5], D5_expected)\n",
"print(\"\\nDo our D(5) and the expected D(5) match?\", D_matches)\n",
"\n",
"# Verify Pi matrix manually\n",
"Pi_matches = True\n",
"for i in range(len(Pi_matrices[5])):\n",
" for j in range(len(Pi_matrices[5][0])):\n",
" if Pi_matrices[5][i][j] != Pi5_expected[i][j]:\n",
" Pi_matches = False\n",
" print(f\"Mismatch at Pi[{i}][{j}]: Calculated={Pi_matrices[5][i][j]}, Expected={Pi5_expected[i][j]}\")\n",
"\n",
"print(\"Do our Pi(5) and the expected Pi(5) match?\", Pi_matches)\n",
"\n",
"if not D_matches:\n",
" print(\"\\nDifferences in D:\")\n",
" diff = D_matrices[5] - D5_expected\n",
" for i in range(len(diff)):\n",
" for j in range(len(diff[0])):\n",
" if diff[i][j] != 0:\n",
" print(f\"Position [{i},{j}]: Calculated={D_matrices[5][i][j]}, Expected={D5_expected[i][j]}\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d6c1c5bc",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "m1",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.4"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment