{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution Notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem: Find the shortest path between two nodes in a graph.\n", "\n", "* [Constraints](#Constraints)\n", "* [Test Cases](#Test-Cases)\n", "* [Algorithm](#Algorithm)\n", "* [Code](#Code)\n", "* [Unit Test](#Unit-Test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "\n", "* Is the graph directed?\n", " * Yes\n", "* Is the graph weighted?\n", " * No\n", "* Can we assume we already have Graph and Node classes?\n", " * Yes\n", "* Are the inputs two Nodes?\n", " * Yes\n", "* Is the output a list of Node keys that make up the shortest path?\n", " * Yes\n", "* If there is no path, should we return None?\n", " * Yes\n", "* Can we assume this is a connected graph?\n", " * Yes\n", "* Can we assume the inputs are valid?\n", " * Yes\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "Input:\n", "* `add_edge(source, destination, weight)`\n", "\n", "```\n", "graph.add_edge(0, 1)\n", "graph.add_edge(0, 4)\n", "graph.add_edge(0, 5)\n", "graph.add_edge(1, 3)\n", "graph.add_edge(1, 4)\n", "graph.add_edge(2, 1)\n", "graph.add_edge(3, 2)\n", "graph.add_edge(3, 4)\n", "```\n", "\n", "Result:\n", "* search_path(start=0, end=2) -> [0, 1, 3, 2]\n", "* search_path(start=0, end=0) -> [0]\n", "* search_path(start=4, end=5) -> None" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "To determine the shorted path in an unweighted graph, we can use breadth-first search keeping track of the previous nodes ids for each node. Previous nodes ids can be a dictionary of key: current node id and value: previous node id.\n", "\n", "* If the start node is the end node, return True\n", "* Add the start node to the queue and mark it as visited\n", " * Update the previous node ids, the previous node id of the start node is None\n", "* While the queue is not empty\n", " * Dequeue a node and visit it\n", " * If the node is the end node, return the previous nodes\n", " * Set the previous node to the current node\n", " * Iterate through each adjacent node\n", " * If the node has not been visited, add it to the queue and mark it as visited\n", " * Update the previous node ids\n", "* Return None\n", "\n", "Walk the previous node ids backwards to get the path.\n", "\n", "Complexity:\n", "* Time: O(V + E), where V = number of vertices and E = number of edges\n", "* Space: O(V + E)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Code" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%run ../graph/graph.py" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "\n", "\n", "class GraphShortestPath(Graph):\n", "\n", " def shortest_path(self, source_key, dest_key):\n", " if source_key is None or dest_key is None:\n", " return None\n", " if source_key is dest_key:\n", " return [source_key]\n", " prev_node_keys = self._shortest_path(source_key, dest_key)\n", " if prev_node_keys is None:\n", " return None\n", " else:\n", " path_ids = [dest_key]\n", " prev_node_key = prev_node_keys[dest_key]\n", " while prev_node_key is not None:\n", " path_ids.append(prev_node_key)\n", " prev_node_key = prev_node_keys[prev_node_key]\n", " return path_ids[::-1]\n", "\n", " def _shortest_path(self, source_key, dest_key):\n", " queue = deque()\n", " queue.append(self.nodes[source_key])\n", " prev_node_keys = {source_key: None}\n", " self.nodes[source_key].visit_state = State.visited\n", " while queue:\n", " node = queue.popleft()\n", " if node.key is dest_key:\n", " return prev_node_keys\n", " prev_node = node\n", " for adj_node in node.adj_nodes.values():\n", " if adj_node.visit_state == State.unvisited:\n", " queue.append(adj_node)\n", " prev_node_keys[adj_node.key] = prev_node.key\n", " adj_node.visit_state = State.visited\n", " return None" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Unit Test" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting test_shortest_path.py\n" ] } ], "source": [ "%%writefile test_shortest_path.py\n", "import unittest\n", "\n", "\n", "class TestShortestPath(unittest.TestCase):\n", "\n", " def test_shortest_path(self):\n", " nodes = []\n", " graph = GraphShortestPath()\n", " for id in range(0, 6):\n", " nodes.append(graph.add_node(id))\n", " graph.add_edge(0, 1)\n", " graph.add_edge(0, 4)\n", " graph.add_edge(0, 5)\n", " graph.add_edge(1, 3)\n", " graph.add_edge(1, 4)\n", " graph.add_edge(2, 1)\n", " graph.add_edge(3, 2)\n", " graph.add_edge(3, 4)\n", "\n", " self.assertEqual(graph.shortest_path(nodes[0].key, nodes[2].key), [0, 1, 3, 2])\n", " self.assertEqual(graph.shortest_path(nodes[0].key, nodes[0].key), [0])\n", " self.assertEqual(graph.shortest_path(nodes[4].key, nodes[5].key), None)\n", "\n", " print('Success: test_shortest_path')\n", "\n", "\n", "def main():\n", " test = TestShortestPath()\n", " test.test_shortest_path()\n", "\n", "\n", "if __name__ == '__main__':\n", " main()" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Success: test_shortest_path\n" ] } ], "source": [ "%run -i test_shortest_path.py" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "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.7.2" } }, "nbformat": 4, "nbformat_minor": 1 }