{ "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 this a directional graph?\n", " * Yes\n", "* Could the graph have cycles?\n", " * Yes\n", " * Note: If the answer were no, this would be a DAG. \n", " * DAGs can be solved with a [topological sort](http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/)\n", "* Are the edges weighted?\n", " * Yes\n", " * Note: If the edges were not weighted, we could do a BFS\n", "* Are the edges all non-negative numbers?\n", " * Yes\n", " * Note: Graphs with negative edges can be done with Bellman-Ford\n", " * Graphs with negative cost cycles do not have a defined shortest path\n", "* Do we have to check for non-negative edges?\n", " * No\n", "* Can we assume this is a connected graph?\n", " * Yes\n", "* Can we assume the inputs are valid?\n", " * No\n", "* Can we assume we already have a graph class?\n", " * Yes\n", "* Can we assume we already have a priority queue class?\n", " * Yes\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "The constraints state we don't have to check for negative edges, so we test with the general case.\n", "\n", "
\n",