{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Find Shortest Path\n\nFinding the shortest path between 2 nodes of a given graph\nusing `shortest_path` function.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import networkx as nx\nimport matplotlib.pyplot as plt\n\n# Create a graph with nodes and edges\nG = nx.Graph()\nG.add_nodes_from([\"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"G\", \"H\"])\nG.add_edge(\"A\", \"B\", weight=4)\nG.add_edge(\"A\", \"H\", weight=8)\nG.add_edge(\"B\", \"C\", weight=8)\nG.add_edge(\"B\", \"H\", weight=11)\nG.add_edge(\"C\", \"D\", weight=7)\nG.add_edge(\"C\", \"F\", weight=4)\nG.add_edge(\"C\", \"I\", weight=2)\nG.add_edge(\"D\", \"E\", weight=9)\nG.add_edge(\"D\", \"F\", weight=14)\nG.add_edge(\"E\", \"F\", weight=10)\nG.add_edge(\"F\", \"G\", weight=2)\nG.add_edge(\"G\", \"H\", weight=1)\nG.add_edge(\"G\", \"I\", weight=6)\nG.add_edge(\"H\", \"I\", weight=7)\n\n# Find the shortest path from node A to node E\npath = nx.shortest_path(G, \"A\", \"E\", weight=\"weight\")\nprint(path)\n\n# Create a list of edges in the shortest path\npath_edges = list(zip(path, path[1:]))\n\n# Create a list of all edges, and assign colors based on whether they are in the shortest path or not\nedge_colors = [\n    \"red\" if edge in path_edges or tuple(reversed(edge)) in path_edges else \"black\"\n    for edge in G.edges()\n]\n\n# Visualize the graph\npos = nx.spring_layout(G)\nnx.draw_networkx_nodes(G, pos)\nnx.draw_networkx_edges(G, pos, edge_color=edge_colors)\nnx.draw_networkx_labels(G, pos)\nnx.draw_networkx_edge_labels(\n    G, pos, edge_labels={(u, v): d[\"weight\"] for u, v, d in G.edges(data=True)}\n)\n\nplt.show()"
      ]
    }
  ],
  "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.12.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}