dijkstra.ipynb

dijkstra.ipynb

{
  "cells": [
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2018-09-02T17:02:34.179505Z",
          "end_time": "2018-09-02T17:02:34.182989Z"
        },
        "collapsed": true,
        "trusted": true
      },
      "cell_type": "code",
      "source": "import logging\nlogger = logging.getLogger()\nlogger.setLevel(logging.DEBUG)",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2018-09-02T17:02:35.155013Z",
          "end_time": "2018-09-02T17:02:35.173803Z"
        },
        "collapsed": true,
        "trusted": true
      },
      "cell_type": "code",
      "source": "f = open(\"dijkstraData.txt\", 'r')\nline = f.readline()\ngraph = {}\ndistances = {}\nwhile line:\n    line_items = line.split(\"\\t\")\n    node, edges = int(line_items[0]), [item.split(\",\") for item in line_items[1:]]\n    if node not in graph:\n        graph[node] = {}\n    for edge in edges:\n        if len(edge) != 2:\n            continue\n        head = int(edge[0])\n        distance = int(edge[1])\n        graph[node][head] = distance\n    line = f.readline()",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2018-09-02T17:02:37.090907Z",
          "end_time": "2018-09-02T17:02:37.115767Z"
        },
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "def get_crossing_edges(graph, explored_nodes, distances):\n    shortest_path = None\n    score = None\n    main_loop_count = 0\n    inner_loop_count = 0\n    for tail, neighbors in graph.iteritems():\n        main_loop_count += 1\n        for head, distance in neighbors.iteritems():\n            inner_loop_count += 1\n            if tail in explored_nodes and head not in explored_nodes:\n                if shortest_path is None:\n                    shortest_path = (tail, head, distance)\n                    score = distances[tail] + distance\n                else:\n                    score_currnet = distances[tail] + distance\n                    if score > score_currnet:\n                        shortest_path = (tail, head, distance)\n                        score = score_currnet\n    log_msg = \"adding path %d-(%d)->%d\" % (shortest_path[0], shortest_path[2], shortest_path[1])\n    logging.debug(log_msg)\n    return shortest_path\n                \n                \ndef dijkstra(graph, source):\n    distances = {}\n    all_nodes = set(graph.keys())\n    explored = set()\n    explored.add(source)\n    distances[source] = 0\n    while explored != all_nodes:\n        tail, head, distance = get_crossing_edges(graph, list(explored), distances)\n        distances[head] = distances[tail] + distance\n        explored.add(head)\n    return distances\n        \n        \n    ",
      "execution_count": 3,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2018-09-02T17:02:39.555933Z",
          "end_time": "2018-09-02T17:02:41.201705Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "distances = dijkstra(graph, 1)",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": "DEBUG:root:adding path 1-(508)->114\nDEBUG:root:adding path 1-(546)->140\nDEBUG:root:adding path 1-(647)->92\nDEBUG:root:adding path 1-(648)->145\nDEBUG:root:adding path 114-(168)->129\nDEBUG:root:adding path 92-(96)->70\nDEBUG:root:adding path 70-(2)->9\nDEBUG:root:adding path 9-(70)->199\nDEBUG:root:adding path 199-(11)->65\nDEBUG:root:adding path 1-(982)->80\nDEBUG:root:adding path 114-(490)->35\nDEBUG:root:adding path 80-(62)->19\nDEBUG:root:adding path 92-(426)->194\nDEBUG:root:adding path 80-(108)->119\nDEBUG:root:adding path 19-(107)->187\nDEBUG:root:adding path 145-(521)->108\nDEBUG:root:adding path 129-(517)->85\nDEBUG:root:adding path 92-(556)->128\nDEBUG:root:adding path 114-(714)->27\nDEBUG:root:adding path 92-(610)->134\nDEBUG:root:adding path 65-(439)->71\nDEBUG:root:adding path 27-(84)->122\nDEBUG:root:adding path 119-(275)->170\nDEBUG:root:adding path 134-(119)->158\nDEBUG:root:adding path 27-(210)->175\nDEBUG:root:adding path 9-(700)->131\nDEBUG:root:adding path 134-(276)->135\nDEBUG:root:adding path 9-(794)->72\nDEBUG:root:adding path 134-(294)->11\nDEBUG:root:adding path 119-(518)->87\nDEBUG:root:adding path 87-(19)->159\nDEBUG:root:adding path 159-(49)->61\nDEBUG:root:adding path 170-(328)->164\nDEBUG:root:adding path 108-(525)->126\nDEBUG:root:adding path 119-(617)->195\nDEBUG:root:adding path 1-(1724)->198\nDEBUG:root:adding path 85-(544)->192\nDEBUG:root:adding path 158-(383)->112\nDEBUG:root:adding path 131-(358)->14\nDEBUG:root:adding path 119-(730)->130\nDEBUG:root:adding path 114-(1318)->103\nDEBUG:root:adding path 119-(741)->154\nDEBUG:root:adding path 9-(1087)->152\nDEBUG:root:adding path 35-(839)->16\nDEBUG:root:adding path 35-(853)->39\nDEBUG:root:adding path 130-(55)->8\nDEBUG:root:adding path 112-(130)->141\nDEBUG:root:adding path 80-(917)->113\nDEBUG:root:adding path 35-(992)->172\nDEBUG:root:adding path 126-(307)->155\nDEBUG:root:adding path 119-(928)->90\nDEBUG:root:adding path 85-(836)->133\nDEBUG:root:adding path 70-(1295)->168\nDEBUG:root:adding path 164-(347)->42\nDEBUG:root:adding path 141-(158)->64\nDEBUG:root:adding path 135-(519)->82\nDEBUG:root:adding path 141-(168)->124\nDEBUG:root:adding path 154-(229)->200\nDEBUG:root:adding path 1-(2069)->173\nDEBUG:root:adding path 72-(541)->153\nDEBUG:root:adding path 198-(366)->28\nDEBUG:root:adding path 61-(448)->163\nDEBUG:root:adding path 108-(972)->143\nDEBUG:root:adding path 163-(18)->44\nDEBUG:root:adding path 72-(604)->157\nDEBUG:root:adding path 11-(594)->183\nDEBUG:root:adding path 157-(7)->26\nDEBUG:root:adding path 14-(373)->118\nDEBUG:root:adding path 1-(2183)->150\nDEBUG:root:adding path 26-(36)->95\nDEBUG:root:adding path 134-(979)->36\nDEBUG:root:adding path 143-(108)->25\nDEBUG:root:adding path 187-(1128)->176\nDEBUG:root:adding path 154-(453)->18\nDEBUG:root:adding path 192-(561)->77\nDEBUG:root:adding path 42-(263)->30\nDEBUG:root:adding path 64-(256)->106\nDEBUG:root:adding path 103-(491)->110\nDEBUG:root:adding path 18-(44)->120\nDEBUG:root:adding path 85-(1147)->189\nDEBUG:root:adding path 158-(969)->181\nDEBUG:root:adding path 92-(1704)->20\nDEBUG:root:adding path 195-(652)->144\nDEBUG:root:adding path 1-(2367)->99\nDEBUG:root:adding path 135-(861)->13\nDEBUG:root:adding path 72-(859)->96\nDEBUG:root:adding path 80-(1417)->115\nDEBUG:root:adding path 77-(105)->160\nDEBUG:root:adding path 95-(231)->196\nDEBUG:root:adding path 145-(1769)->136\nDEBUG:root:adding path 85-(1227)->53\nDEBUG:root:adding path 130-(615)->178\nDEBUG:root:adding path 1-(2437)->49\nDEBUG:root:adding path 187-(1291)->165\nDEBUG:root:adding path 64-(414)->86\nDEBUG:root:adding path 25-(219)->132\nDEBUG:root:adding path 65-(1652)->102\nDEBUG:root:adding path 71-(1229)->138\nDEBUG:root:adding path 9-(1753)->63\nDEBUG:root:adding path 181-(158)->51\nDEBUG:root:adding path 196-(88)->188\nDEBUG:root:adding path 51-(22)->5\nDEBUG:root:adding path 114-(2027)->111\nDEBUG:root:adding path 200-(475)->67\nDEBUG:root:adding path 114-(2032)->107\nDEBUG:root:adding path 113-(652)->33\nDEBUG:root:adding path 172-(561)->104\nDEBUG:root:adding path 194-(1483)->162\nDEBUG:root:adding path 53-(153)->62\nDEBUG:root:adding path 107-(52)->60\nDEBUG:root:adding path 113-(697)->190\nDEBUG:root:adding path 1-(2597)->117\nDEBUG:root:adding path 53-(179)->7\nDEBUG:root:adding path 124-(552)->56\nDEBUG:root:adding path 155-(609)->37\nDEBUG:root:adding path 18-(332)->142\nDEBUG:root:adding path 33-(67)->125\nDEBUG:root:adding path 87-(1022)->167\nDEBUG:root:adding path 144-(285)->3\nDEBUG:root:adding path 165-(208)->23\nDEBUG:root:adding path 53-(236)->34\nDEBUG:root:adding path 86-(195)->84\nDEBUG:root:adding path 167-(52)->146\nDEBUG:root:adding path 188-(198)->184\nDEBUG:root:adding path 86-(259)->75\nDEBUG:root:adding path 154-(901)->41\nDEBUG:root:adding path 162-(201)->48\nDEBUG:root:adding path 140-(2230)->169\nDEBUG:root:adding path 160-(383)->91\nDEBUG:root:adding path 41-(63)->78\nDEBUG:root:adding path 128-(1602)->123\nDEBUG:root:adding path 30-(503)->79\nDEBUG:root:adding path 150-(634)->52\nDEBUG:root:adding path 64-(771)->121\nDEBUG:root:adding path 123-(13)->6\nDEBUG:root:adding path 64-(810)->57\nDEBUG:root:adding path 121-(44)->55\nDEBUG:root:adding path 18-(589)->148\nDEBUG:root:adding path 120-(556)->185\nDEBUG:root:adding path 67-(371)->12\nDEBUG:root:adding path 123-(132)->46\nDEBUG:root:adding path 163-(818)->15\nDEBUG:root:adding path 162-(391)->59\nDEBUG:root:adding path 56-(361)->100\nDEBUG:root:adding path 34-(315)->2\nDEBUG:root:adding path 71-(1711)->81\nDEBUG:root:adding path 70-(2236)->47\nDEBUG:root:adding path 119-(1914)->32\nDEBUG:root:adding path 78-(212)->73\nDEBUG:root:adding path 121-(195)->156\nDEBUG:root:adding path 160-(624)->180\nDEBUG:root:adding path 19-(2002)->88\nDEBUG:root:adding path 49-(619)->4\nDEBUG:root:adding path 110-(751)->197\nDEBUG:root:adding path 70-(2366)->149\nDEBUG:root:adding path 108-(1942)->17\nDEBUG:root:adding path 46-(199)->193\nDEBUG:root:adding path 129-(2464)->109\nDEBUG:root:adding path 13-(758)->50\nDEBUG:root:adding path 96-(807)->10\nDEBUG:root:adding path 143-(1079)->76\nDEBUG:root:adding path 199-(2446)->89\nDEBUG:root:adding path 135-(1752)->127\nDEBUG:root:adding path 143-(1171)->43\nDEBUG:root:adding path 180-(341)->105\nDEBUG:root:adding path 4-(313)->54\nDEBUG:root:adding path 142-(777)->66\nDEBUG:root:adding path 57-(558)->94\nDEBUG:root:adding path 169-(662)->45\nDEBUG:root:adding path 4-(399)->31\nDEBUG:root:adding path 95-(1278)->147\nDEBUG:root:adding path 57-(656)->116\nDEBUG:root:adding path 67-(980)->98\nDEBUG:root:adding path 157-(1393)->101\nDEBUG:root:adding path 111-(1005)->29\nDEBUG:root:adding path 85-(2349)->93\nDEBUG:root:adding path 88-(502)->38\nDEBUG:root:adding path 72-(2019)->174\nDEBUG:root:adding path 51-(1096)->137\nDEBUG:root:adding path 193-(494)->21\nDEBUG:root:adding path 102-(1172)->69\nDEBUG:root:adding path 199-(2838)->24\nDEBUG:root:adding path 125-(1050)->58\nDEBUG:root:adding path 180-(664)->179\nDEBUG:root:adding path 195-(2099)->186\nDEBUG:root:adding path 54-(438)->182\nDEBUG:root:adding path 35-(2816)->166\nDEBUG:root:adding path 92-(3182)->177\nDEBUG:root:adding path 67-(1394)->171\nDEBUG:root:adding path 165-(1555)->83\nDEBUG:root:adding path 132-(1560)->22\nDEBUG:root:adding path 71-(2826)->40\nDEBUG:root:adding path 155-(2100)->139\nDEBUG:root:adding path 75-(1403)->191\nDEBUG:root:adding path 83-(162)->151\nDEBUG:root:adding path 64-(2201)->97\nDEBUG:root:adding path 121-(1468)->74\nDEBUG:root:adding path 144-(2277)->68\nDEBUG:root:adding path 88-(1726)->161\n"
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2018-09-02T17:02:45.371531Z",
          "end_time": "2018-09-02T17:02:45.376468Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "nodes_to_check_distances = [7,37,59,82,99,115,133,165,188,197]\nstr_distances = \",\".join([str(distances[item]) for item in nodes_to_check_distances])\nprint str_distances",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": "2599,2610,2947,2052,2367,2399,2029,2442,2505,3068\n"
        }
      ]
    },
    {
      "metadata": {
        "collapsed": true,
        "trusted": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python2",
      "display_name": "Python 2",
      "language": "python"
    },
    "language_info": {
      "mimetype": "text/x-python",
      "nbconvert_exporter": "python",
      "name": "python",
      "pygments_lexer": "ipython2",
      "version": "2.7.10",
      "file_extension": ".py",
      "codemirror_mode": {
        "version": 2,
        "name": "ipython"
      }
    },
    "gist": {
      "id": "",
      "data": {
        "description": "dijkstra.ipynb",
        "public": true
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}