DataAlgo2020_008(1-N_ShortestPath)ext.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-008(１対Ｎの最短経路問題)ext",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyP5axTQ40T7isHzAoBC2+X0",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kameda-yoshinari/DataAlgo2020/blob/master/DataAlgo2020_008(%EF%BC%91%E5%AF%BE%EF%BC%AE%E3%81%AE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C)ext.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yRmydXneMgT8",
        "colab_type": "text"
      },
      "source": [
        "# 4.2. １対Ｎの最短経路問題\n",
        "\n",
        "ここではある頂点を開始頂点としたときの最短経路問題とそれを解くDijkstraのアルゴリズムについて学ぶ．\n",
        "\n",
        "**いつもの約束**  \n",
        "１つのコードセルだけの実行は Ctrl + Enter．  \n",
        "エディタで「インデント幅（スペース）は4で表示」「行番号を表示」「インデントガイドを表示」．  \n",
        "挿入図は Google Colaboratory  以外では見れない可能性あり．  \n",
        "内部では日本語はUTF-8で表現されている．\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CdQdV_MJIlce",
        "colab_type": "text"
      },
      "source": [
        "# 準備\n",
        "\n",
        "インスタンスに接続し起動する．  \n",
        "下記の手順でGoogle Driveをマウントする．  \n",
        "マウント先に移動し，作業フォルダとする．  \n",
        "これによって，インスタンスがリセットされてもGoogle Drive内にファイルが保存されるようにする．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DMtqXRXJIPMR",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!echo \"Google Driveをマウントします\"\n",
        "from google.colab import drive \n",
        "drive.mount('/content/drive')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SABzmuELIaj2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!echo \"今回の作業用フォルダを作成しそこに移動します\"\n",
        "%cd /content/drive/My\\ Drive/\n",
        "%mkdir -p 202004_DataAlgo/DA2020_008\n",
        "%cd       202004_DataAlgo/DA2020_008\n",
        "!ls\n",
        "!echo \"日本時間表示\"\n",
        "!rm /etc/localtime\n",
        "!ln -s /usr/share/zoneinfo/Japan /etc/localtime\n",
        "!date"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NINxYWNgOSaw",
        "colab_type": "text"
      },
      "source": [
        "本節での説明には，グラフ6を利用する．  \n",
        "頂点数は8．無向グラフ．ループなし．重みは全て正．  \n",
        "プログラムの解析用に，グラフ7, グラフ8も用意しておく．\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tErWQzIr6Ttp",
        "colab_type": "text"
      },
      "source": [
        "![da2020-graph6](https://user-images.githubusercontent.com/45651568/84224948-d3d8ff80-ab18-11ea-8ade-83985ae9cd79.jpg)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rz4_9z4rOQu4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile graph6.h\n",
        "// 8 nodes, undirected, no loop, positive weight.\n",
        "// NC means no edges.\n",
        "// NC will be treated as \"inifinity\" on searching the shortest path. \n",
        "#define N 8\n",
        "#define NC 9999 // this big value means both no path and infinity \n",
        "int edge[N][N] = {\n",
        "//     0   1   2   3   4   5   6   7\n",
        "\t{ NC,100, NC, NC,145,200, NC, NC}, // 0\n",
        "\t{100, NC, 23, NC, NC, 80, NC, 70}, // 1\n",
        "\t{ NC, 23, NC, 21, NC, 45, 37, NC}, // 2\n",
        "\t{ NC, NC, 21, NC, NC, NC, 18,  5}, // 3\n",
        "\t{145, NC, NC, NC, NC, 20, NC, NC}, // 4\n",
        "\t{200, 80, 45, NC, 20, NC,  2, NC}, // 5\n",
        "\t{ NC, NC, 37, 18, NC,  2, NC,  1}, // 6\n",
        "\t{ NC, 70, NC,  5, NC, NC,  1, NC}  // 7\n",
        "};"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "68fKClFZFJW5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile graph7.h\n",
        "// 4 nodes, directed, positive weight.\n",
        "// NC means no edges.\n",
        "// NC will be treated as \"inifinity\" on searching the shortest path. \n",
        "#define N 4\n",
        "#define NC 9999 // this big value means no path\n",
        "int edge[N][N] = {\n",
        "//     0   1   2   3\n",
        "\t{ NC, 10, NC, 40}, // 0\n",
        "\t{ NC, NC, NC, 20}, // 1\n",
        "\t{ NC, NC, NC, NC}, // 2\n",
        "\t{ NC, NC, NC, NC}, // 3\n",
        "};"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZKMrM5a2OUv4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile graph8.h\n",
        "// 12 nodes, directed, positive weight.\n",
        "// NC means no edges.\n",
        "// NC will be treated as \"inifinity\" on searching the shortest path. \n",
        "#define N 12\n",
        "#define NC 9999 // this big value means no path\n",
        "int edge[N][N] = {\n",
        "    { 0, 4,NC,NC, 3,NC,NC,NC,NC,NC,NC,NC},\n",
        "    { 4, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC,NC},\n",
        "    {NC, 1, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC},\n",
        "    {NC,NC, 1, 0,NC,NC,NC,NC,NC,NC,NC,NC},\n",
        "    { 3,NC,NC,NC, 0, 1,NC,NC, 1,NC,NC,NC},\n",
        "    {NC,NC,NC,NC, 1, 0, 2,NC,NC, 2, 3,NC},\n",
        "    {NC, 2,NC,NC,NC, 2, 0,NC,NC,NC, 3,NC},\n",
        "    {NC,NC, 2,NC,NC,NC,NC, 0,NC,NC,NC,NC},\n",
        "    {NC,NC,NC,NC, 1,NC,NC,NC, 0,NC,NC,NC},\n",
        "    {NC,NC,NC,NC,NC, 2,NC,NC,NC, 0,NC,NC},\n",
        "    {NC,NC,NC,NC,NC, 3, 3,NC,NC,NC, 0, 1},\n",
        "    {NC,NC,NC,NC,NC,NC,NC,NC,NC,NC, 1, 0}\n",
        "};"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4s3BWazcz1FB",
        "colab_type": "text"
      },
      "source": [
        "# １対Ｎの最短経路問題を解くDijkstraのアルゴリズム\n",
        "\n",
        "**内容**\n",
        "\n",
        "グラフとして重み付き有向グラフを考える．辺に重みとして数値が付与されている．\n",
        "本節では，辺の重みは正値とする．\n",
        "隣接する頂点aと頂点bの間の辺の重みをedge(a,b)で表現する．edge(a,b)は正値である．  \n",
        "\n",
        "最短経路問題とは，与えられた重み付き有向グラフにおいて，指定された２頂点間を結ぶ道を考える時，最も重みの軽い道の重みを求める問題である．ここでは，頂点Aから頂点Bへの「道」には，同じ頂点は高々一度しか現れないものとする．ある道（経路）が与えられた時，その辺の重みの合計のことを経路（道）の重み或いは経路値と呼ぶ．\n",
        "\n",
        "指定された２頂点間に道がない場合は，その経路値は無限大として扱う．\n",
        "\n",
        "解を示す道（経路）ももちろん求めるべきである．\n",
        "\n",
        "一般に，指定された２頂点について最短経路問題を解く計算時間と，開始頂点を指定してその他すべての頂点への（１対Ｎの）最短経路問題を解く計算時間はオーダー表現において同じであるとされている．（到着頂点を指定してその他すべての頂点を開始頂点にした場合でも同じ．）\n",
        "\n",
        "**Dijkstraのアルゴリズム**\n",
        "\n",
        "１対Ｎの最短経路問題を解くアルゴリズムとして，Dijkstra（ダイクストラ）のアルゴリズムを学習する．\n",
        "\n",
        "Dijkstraのアルゴリズムは，貪欲法(Greedy algorithm)の１つとして知られる．\n",
        "\n",
        ">**（貪欲法）**\n",
        ">\n",
        ">貪欲法の定義の詳細は本授業では省くが，簡単に言えば，解を求める途中で，その時点で最適と思われる方に進む方法である．\n",
        ">\n",
        ">例えば，街で目的地の高い建物が見えているとき，その方向に向かって真っすぐ進む方法がこの一例として考えられる．途中に壁があったり一方通行があったりすると，真っすぐ進むのはかえって結果的に遠回りになるかもしれない．しかし，それはあとになってしかわからないことだと割り切ってその場では真っすぐ進むことはよくあるだろう．人間の普段の行動によく似ているとも言える．\n",
        ">\n",
        ">貪欲法に基づくアルゴリズムでは，一般には最適解を得る保証はない．しかしながら，Dijkstraのアルゴリズムは数少ない例外である．\n",
        "すなわち，Disktraのアルゴリズムは貪欲法でありながら，このアルゴリズムによって最短経路問題の最適解が得られることが証明されている．\n",
        "\n",
        "以下では，最短を最小と置き換えて説明する．\n",
        "\n",
        "1. 開始頂点から開始頂点への経路値は0とする．開始頂点から他の頂点の経路値については全て無限大とする（これは現在たどり着けないという意味ではなく，経路値についてまだ全く未確認であるという状況を表していると考えると分かりやすいだろう）．\n",
        "2. 全ての頂点を未処理頂点集合Uの要素とする．\n",
        "3. Uの中で経路値が最小の頂点kを選ぶ．（1.の設定から，初めて3.に来たときは開始頂点が選ばれることになる．）\n",
        "4. 頂点kをUから削除する．\n",
        "5. Uの中で頂点kに隣接する頂点について，頂点kを経由して到達する経路値のほうが小さければ，その頂点の経路値を更新する．\n",
        "6. 未処理頂点集合Uが空集合になるまで，3.から5.を繰り返す．\n",
        "7. 各頂点の経路値がそのまま開始頂点からの最小経路値となる．\n",
        "\n",
        "Dijkstraのアルゴリズムは直感的な解決方法に似ていると感じはしないだろうか．順を追って実際にグラフ6で処理を実行してみればその感覚はさらに強まるだろう．\n",
        "\n",
        "グラフ6での処理進行については，次図を参照されたい．\n",
        "図中において，頂点枠内の数字は経路値を示している．\n",
        "三段になっている各小図は，上段が3.，中段が4.と5.の新しい経路値の計算まで，下段が5.の経路値の更新に相当している．\n",
        "中段では，新しく計算できるようになった経路と頂点を破線で示し，その経路値を頂点枠中の下側に示している．5.で小さい方の値を選択することで下段の状態になる．\n",
        "辺の表示が有向辺に切り替わるのは，経路値を実現する経路を示すためである．\n",
        "開始頂点0から見て，曲線の外側が未処理頂点集合Uを表している．\n",
        "\n",
        "**実装**\n",
        "\n",
        "残念ながら，Dijkstraのアルゴリズムは，C言語での実装に不向きなものの一つである．\n",
        "\n",
        "その理由は，処理に集合を用いていることである．C言語の仕様には集合を直接扱える構造がない．  \n",
        "（深さ優先探索の時はスタック構造が関数呼び出しに埋め込まれていたことを思い出そう）\n",
        "\n",
        "そのため，集合を扱う関数群を用意してから，アルゴリズムの実装に取り掛かるという２段構成が必要になる．\n",
        "\n",
        "**備考（雑談）**\n",
        "\n",
        "私が学生時代に諸君らと同じように初めてDiskstraのアルゴリズムを習った時，教えて下さった先生はfortran言語を使った数値解析が専門であった．\n",
        "その先生が，\"Dijkstra\"と板書されたときにやおらこちらに向かって「すごくいい名前ですよね？気に入っているんです」とおっしゃられた．\n",
        "何を言い出したのだろう，と不思議に思った．\n",
        "すると，先生は，「名前に\"i\",\"j\",\"k\"がこの順に入っている．これはプログラミングの申し子のような名前ですごくいいと思うんです」と．\n",
        "それから30年近く経つが，その時の先生のとても楽しそうな顔が今でも忘れられない．\n",
        "ああ，本当にこの先生はこういうことが好きなのだな，大学の先生とはこういう方なのだな，と強く思ったことを今でも覚えている．\n",
        "だからなんだと言われると困るが，不思議な縁で大学の教員となった今，こうしたことを伝えておこうと思うのである．\n",
        "（プログラミングでループ変数は伝統的に i を用いる．これは iteration/繰り返し の頭文字である．２重ループ，３重ループとなると，それに続くアルファベットを使うのが伝統であるので，３重ループではi,j,kが順に使われることが多い．数値解析などでは多重ループがよく出てくるので，i,j,kを連続して使うことはままある）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Iqijdp1MXd8N",
        "colab_type": "text"
      },
      "source": [
        "![da2020-dijkstra-bitmap](https://user-images.githubusercontent.com/45651568/84225202-7e512280-ab19-11ea-8d73-97296fa1c64a.jpg)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0_o0avWIHZqC",
        "colab_type": "text"
      },
      "source": [
        "# Dijkstraのアルゴリズムに基づくプログラム\n",
        "\n",
        "**目標**\n",
        "\n",
        "正値重みの辺で構成される有向グラフにおいて，ある頂点を開始頂点としたときの各頂点への最小経路値とその経路を求めるＣプログラムを作成する．\n",
        "\n",
        "**説明**\n",
        "\n",
        "Dijkstraのアルゴリズム本体は一つのユーザ定義関数 find_shortest_diskstra() で実装する．集合操作を別ソースファイルで記述する．\n",
        "集合操作については，これまでに学習した QueueLib / StackLib と同じ要領で SetLib として作成する．\n",
        "\n",
        "トップダウンプログラミングに馴染めるよう，今回は SetLib_J.h を先に書き，必要なプログラムを実際に実装する形を取ってみよう．\n",
        "\n",
        "1. SetLib_J.h ... 関数のプロトタイプ宣言．各関数に必要とされる集合操作を説明しておく．どのような集合操作が必要かは，Dijkstraのアルゴリズムを精査して抜き出す．\n",
        "2. SetLib_J.c ... 各関数の実体を実装する．\n",
        "3. shortest-dijkstra_J.c ... 引数を解析するmain()関数，上述のfind_shortest_dijkstra() の他，経路値情報を表示する関数も用意する．\n",
        "\n",
        "**コード**\n",
        "\n",
        "SetLib_J.h でプロトタイプ宣言を並べたあと，そのファイルをコピーして SetLib_J.c とし，関数名・引数に続いて実際にそれぞれの関数についてのプログラム記述していく形が取れれば，トップダウンプログラミングが出来ていると言えよう．\n",
        "\n",
        "**備考**\n",
        "\n",
        "集合操作にどのような関数が必要か見通すためには，Dijkstraのアルゴリズムを正確に理解できていることが必須である．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LBw5JAQsnSBC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile SetLib_J.h\n",
        "// Set management\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "\n",
        "// １つの集合のみ扱う．\n",
        "// その集合の要素は非負の整数とする．\n",
        "\n",
        "// 集合の初期化\n",
        "// 引数：確保する要素数\n",
        "// 返値：成功...確保した整数配列のポインタ, 失敗...NULL\n",
        "int *initset(int );\n",
        "\n",
        "// 集合への追加\n",
        "// 指定された（非負）整数を集合に追加する．\n",
        "// 返値：成功 ... 指定された整数, 失敗 ... 負値\n",
        "int addelement(int );\n",
        "\n",
        "// 集合から要素vを削除\n",
        "// 指定された整数を集合から削除する．\n",
        "// 返値：成功 ... 指定された整数, 失敗 ... 負値\n",
        "int deleteelement(int );\n",
        "\n",
        "// 集合の要素一覧の入手\n",
        "int obtainelementlist(int *, int );\n",
        "\n",
        "// 集合の状態表示\n",
        "int showset(void);\n",
        "\n",
        "// 集合の全表示（通常意味はない）\n",
        "int showallset(void);\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TbuQlUcCnxD2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile SetLib_J.c\n",
        "// Set management\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // calloc()\n",
        "#include \"SetLib_J.h\" // プロトタイプ宣言の整合確認\n",
        "\n",
        "int *setU = NULL;  // 頂点集合 U を表す配列\n",
        "int setsize = 0; // 集合 U の最大要素数\n",
        "int numset = 0; // 集合 U の現在の要素数 (配列先頭から)\n",
        "\n",
        "// 集合の初期化\n",
        "// 引数：確保する要素数\n",
        "// 返値：成功...確保した整数配列のポインタ, 失敗...NULL\n",
        "int *initset(int n) {\n",
        "\tsetU = calloc(n, sizeof(*setU));\n",
        "\tsetsize = n;\n",
        "\tif (setU == NULL) {\n",
        "\t\tprintf(\"【失敗】 %d要素分の集合用配列を確保できませんでした．\\n\", n);\n",
        "\t\tsetsize = 0;\n",
        "\t}\n",
        "\treturn setU;\n",
        "}\n",
        "\n",
        "// 集合への追加\n",
        "// 指定された（非負）整数を集合に追加する．\n",
        "// 返値：成功 ... 指定された整数, 失敗 ... 負値\n",
        "int addelement(int v) {\n",
        "    if (setU == NULL) {\n",
        "        printf(\"【失敗】 集合が用意できていません．\\n\");\n",
        "        return -1;\n",
        "    } else if (numset >= setsize) {\n",
        "        printf(\"【失敗】 %d要素確保してあった集合領域を使い果たしてしまいました．\\n\", setsize);\n",
        "        return -2;\n",
        "    }\n",
        "    setU[numset] = v;\n",
        "    numset++;\n",
        "    return 0;\n",
        "}\n",
        "\n",
        "// 集合から要素vを削除\n",
        "// 指定された整数を集合から削除する．\n",
        "// 返値：成功 ... 指定された整数, 失敗 ... 負値\n",
        "\n",
        "int deleteelement(int v) {\n",
        "    int setindex = -1;\n",
        "    int i;\n",
        "\n",
        "    if (setU == NULL) {\n",
        "        printf(\"【失敗】 集合が用意できていません．\\n\");\n",
        "        return -1;\n",
        "    } else if (numset <= 0) {\n",
        "        printf(\"【報告】 空集合なので要素を取り出せません．\\n\");\n",
        "        return -2;\n",
        "    } else {\n",
        "        // 集合配列内の要素vが存在する位置を探索\n",
        "        for (i = 0; i < numset; i++) {\n",
        "            if (setU[i] == v)\n",
        "                setindex = i;\n",
        "        }\n",
        "        if (setindex < 0) {\n",
        "            printf(\"【報告】要素%dが存在しませんでした．\\n\", v);\n",
        "            return -3;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\t// U: setU[0, ... ,numset-1] において setU[setindex] が抜けるので、配列 setU[]の端の setU[numset-1]を代入して端を捨てる\n",
        "\tsetU[setindex] = setU[numset - 1];\n",
        "\tnumset--;\n",
        "\n",
        "    return v;\n",
        "}\n",
        "\n",
        "// 集合の要素一覧の入手\n",
        "int obtainelementlist(int *array, int n) {\n",
        "    int i;\n",
        "\n",
        "    if (setU == NULL) {\n",
        "        printf(\"【失敗】 集合が用意できていません．\\n\");\n",
        "        return -1;\n",
        "    } else if (n < numset) {\n",
        "        printf(\"【失敗】 用意した配列が小さ過ぎます．%d, %d\\n\", n, numset);\n",
        "        return -2;\n",
        "    }\n",
        "\n",
        "    for (i = 0; i < numset; i++) {\n",
        "        array[i] = setU[i];\n",
        "    }\n",
        " \n",
        "    return numset;\n",
        "}\n",
        "\n",
        "// 集合の状態表示\n",
        "int showset(void) {\n",
        "    int i;\n",
        "\n",
        "    if (setU == NULL) {\n",
        "        printf(\"【失敗】 集合が用意できていません．\\n\");\n",
        "        return -1;\n",
        "    }\n",
        "\n",
        "    printf(\"setsize = %d, number of elements = %d\\n\", setsize, numset);\n",
        "    for (i = 0; i < numset; i++) {\n",
        "        printf(\"%d \", setU[i]);\n",
        "    }\n",
        "    printf(\"\\n\");\n",
        "\n",
        "    return numset;\n",
        "}\n",
        "\n",
        "// 集合の全表示（通常意味はない）\n",
        "int showallset(void) {\n",
        "    int i;\n",
        "\n",
        "    if (setU == NULL) {\n",
        "        printf(\"【失敗】 集合が用意できていません．\\n\");\n",
        "        return -1;\n",
        "    }\n",
        "\n",
        "    printf(\"setsize = %d, number of elements = %d\\n\", setsize, numset);\n",
        "    for (i = 0; i < setsize; i++) {\n",
        "\t\tif (i == numset)\n",
        "\t\t\tprintf(\"| \");\n",
        "        printf(\"%d \", setU[i]);\n",
        "    }\n",
        "    printf(\"\\n\");\n",
        "    return setsize;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qNnLPiCuo6LG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -c SetLib_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Eo2CM8EqZi97",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile shortest-dijkstra_J.c\n",
        "// Shortest path by Dijkstra\n",
        "//    2020/05/30 kameda\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"SetLib_J.h\"\n",
        "#include \"graph6.h\" // edge[][], N, NC\n",
        "\n",
        "typedef struct {\n",
        "\tint cost; // 現時点でこの頂点に到達するのにかかると思われる最安コスト cost\n",
        "\tint from; // 最短経路利用時，この頂点には 頂点from から来る\n",
        "} CostFrom;\n",
        "\n",
        "CostFrom nodeinfo[N]; // 到着頂点i に対する最短経路情報\n",
        "\n",
        "// 頂点状態の表示\n",
        "void print_node_status(char *show_str, int show_v){\n",
        "\tint i;\n",
        "\t\n",
        "\tprintf(\"%s at %d:\", show_str, show_v);\n",
        "\tprintf(\" cost(\");\n",
        "\tfor (i = 0; i < N; i++)\n",
        " \t\tif (nodeinfo[i].cost == NC) \n",
        "   \t\t\tprintf(\"--- \");\n",
        "\t\telse\n",
        "\t\t\tprintf(\"%3d \", nodeinfo[i].cost);\n",
        "\tprintf(\") from(\");\n",
        "\tfor (i = 0; i < N; i++)\n",
        " \t\tprintf(\"%2d \", nodeinfo[i].from);\n",
        "\tprintf(\")\\n\");\n",
        "\n",
        "\tshowset();\n",
        "\treturn ;\n",
        "}\n",
        "\n",
        "// 始点 StartNode から 他の全ての頂点への最短路を探す\n",
        "void find_shortest_dijkstra(int StartNode){\n",
        "\tint v; // 頂点\n",
        "\tint i;\n",
        "\tint restelements = 0; // 未処理の頂点数\n",
        "\tint restS[N]; // 未処理頂点のリスト（個数はrestelements）\n",
        "\tint min_node; // 経路が暫定最短となる頂点\n",
        "\tint min_cost; // その頂点min_nodeまでの暫定最短経路値\n",
        "\t\n",
        "\t// 集合 U に開始頂点以外を追加\n",
        "\tprintf(\"Dijkstra: 集合を%d要素分確保します．\\n\", N);\n",
        "\tinitset(N);\n",
        "\tfor (v = 0; v < N; v++) {\n",
        "\t\taddelement(v);\n",
        "\t\trestelements++;\n",
        "\t}\n",
        "\n",
        "\t// 初期化\n",
        "\t// 開始頂点 StartNode\n",
        "\t// 開始頂点以外の初期解（コスト）は無限大(NC)\n",
        "\tprintf(\"Dijkstra: 初期化します．\\n\");\n",
        "\tfor (v = 0; v < N; v++) {\n",
        "\t\tif (v == StartNode){\n",
        "\t\t\tnodeinfo[v].cost = 0;\n",
        "\t\t\tnodeinfo[v].from = StartNode;\n",
        "\t\t} else {\n",
        "\t\t\tnodeinfo[v].cost = NC;  \n",
        "\t\t\tnodeinfo[v].from = -1; // どこから行くわけでもない\t  \n",
        "\t\t}\n",
        "\t}\n",
        "\n",
        "\t// いよいよスタート\n",
        "\tprint_node_status(\"Start\", 0);\n",
        "\twhile (restelements > 0) {\n",
        "\t\t  \n",
        "\t  \tprint_node_status(\"Loop \", restelements);\n",
        "\n",
        "\t\t// 未処理頂点集合を獲得\n",
        "\t\tobtainelementlist(restS, N);\n",
        "\t\t\n",
        "\t\t// 集合 U の中で、最小コストを与える頂点(min_node)を探す\n",
        "\t\t// 頂点(min_node)はsetU[]のmin_node_index番目の要素として格納されていることに注意\n",
        "\t\t// 探すにあたって、まずsetU[]の先頭要素を、暫定的に最小コストを与える頂点と仮定\n",
        "\t\tmin_node = restS[0]; \n",
        "\t\tmin_cost = nodeinfo[min_node].cost; \n",
        "\t\tfor (i = 1; i < restelements; i++) {\n",
        "\t\t\tv = restS[i];\n",
        "\t\t\tif (nodeinfo[v].cost < min_cost) {\n",
        "\t\t\t\tmin_node = v;\n",
        "\t\t\t\tmin_cost = nodeinfo[v].cost;\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "\t\tprintf(\"未処理頂点集合内で最小の頂点 %d コスト %d\\n\",min_node, min_cost);\n",
        "\n",
        "\t\t// 未処理頂点集合から min_node を削除\n",
        "\t\tdeleteelement(min_node);\n",
        "\t\trestelements--;\n",
        "\n",
        "\t\t// 未処理頂点集合を入手\n",
        "\t\tobtainelementlist(restS, N);\n",
        "\n",
        "\t\t// 未処理頂点集合において、新しく見つかった min_node 経由でコストが下がる場合はコストを書き換え\n",
        "\t\t// 未処理頂点集合のうち、 min_nodeからの経路があるものだけが検査対象\n",
        "\t\tfor (i = 0; i < restelements; i++) {\n",
        "\t\t\tv = restS[i]; // 検査対象の頂点\n",
        "\t\t\tif (edge[min_node][v] > 0) {\n",
        "\t\t\t\tif (nodeinfo[min_node].cost + edge[min_node][v] < nodeinfo[v].cost) {\n",
        "\t\t\t\t\tnodeinfo[v].cost = nodeinfo[min_node].cost + edge[min_node][v];\n",
        "\t\t\t\t\tnodeinfo[v].from = min_node;\n",
        "\t\t\t\t}\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "\t}\n",
        "\n",
        "\t// 目的地 v への最小コストとそこへ至る「最短経路」の表示\n",
        "\tfor (v = 0; v < N; v++) {\n",
        "\t\tprintf(\"To %2d : \", v);\n",
        "\t\tif (v == StartNode) {\n",
        "\t\t\tprintf(\"----\");\n",
        "\t\t} else if (nodeinfo[v].cost == NC) {\n",
        "\t\t\tprintf(\"No path\");\n",
        "\t\t} else {\n",
        "\t\t\tint s;\n",
        "\t\t\tprintf(\"cost %3d : \", nodeinfo[v].cost);\n",
        "\t\t\tfor (s = v; s != StartNode; s = nodeinfo[s].from)\n",
        "\t\t\t\tprintf(\"%2d <- \", s);\n",
        "\t\t\tprintf(\"%2d\", StartNode);\n",
        "\t\t}\n",
        "\t\tprintf(\"\\n\");\n",
        "\t}\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "    int startnode = 0;\n",
        "\n",
        "    if (argc == 1) {\n",
        "        printf(\"指定がなかったので頂点0を開始頂点にします．\\n\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\\n\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tfind_shortest_dijkstra(startnode); // 開始頂点番号を引数にして最短経路探索を開始\n",
        "\n",
        "\treturn 0;\n",
        "}\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zhechXUNbvva",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "コンパイルしてエラーが無いことを確認．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5gxNiHT-bvEd",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -c shortest-dijkstra_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UcFL-3AR8XSu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o shortest-dijkstra_J shortest-dijkstra_J.o SetLib_J.o"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CxBI4UbEcB9L",
        "colab_type": "text"
      },
      "source": [
        "実行．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O3zzVD4tcA3h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!./shortest-dijkstra_J 0    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DY_MbwoPf_9h",
        "colab_type": "text"
      },
      "source": [
        "# 節末課題\n",
        "\n",
        "1. 最短経路の表示の仕組み  \n",
        "shortest_dijkstra プログラムにおいて，それぞれの頂点への最小経路値を実現する経路を表示する仕組みを説明せよ．\n",
        "このとき，構造体CostFromのメンバ from に格納されている値について言及すること．\n",
        "\n",
        "\n",
        "2. 計算量  \n",
        "shortest_diskstra プログラムの時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "3. 重みが零の辺  \n",
        "グラフ中に重みが0の辺があった場合，最短経路問題に与える影響について論ぜよ．\n",
        "\n",
        "\n",
        "4. 閉路の実際上の扱い  \n",
        "与えるグラフに閉路が存在してはならないが，実際には上記のプログラムに閉路が含まれるグラフを与えても実行すると結果が出てしまう．これは本プログラムがグラフの解釈を都合のよいように勝手に変えているからと考えることができる．  \n",
        "それでは，本プログラムでは，閉路が存在するとき，それをどう解釈しているのか，説明を試みよ．\n",
        "\n",
        "5. エラーハンドリング  \n",
        "SetLibで定義された関数を使うときに，１か所を除いてエラーハンドリングをしていない．エラーハンドリングしている個所を示せ．他にエラーハンドリングすべき箇所を示せ．そのうちの１か所（最初）について，対策をした改変例を示せ．\n",
        "\n",
        "\n",
        "6. SetLib関数群における高速化  \n",
        "SetLibにおいて，集合の初期化を要素数Nで行った場合に，その要素を0からN-1に限定すると，SetLibの各関数を高速化することができる．deleteelement()関数を例に，時間計算量をO(N)からO(1)にする方策について示せ．\n",
        "\n",
        "\n",
        "# 出典\n",
        "\n",
        "筑波大学工学システム学類  \n",
        "データ構造とアルゴリズム  \n",
        "担当：亀田能成  \n",
        "2020/06/07.  \n",
        "2020/06/10. (ext) 図をgithubの外部リンク化．\n",
        "\n"
      ]
    }
  ]
}