westoshy
4/30/2018 - 10:48 AM

ダイクストラ法

ダイクストラ法

大学のネットワークか何かの講義の課題でダイクストラ法をお題にしてプログラムとして書いたものです.

ダイクストラ法で山手線の内側にある駅を最短パスで結ぶことになっています. 経路の重みは時間でやっているみたいです.

#include <stdio.h>
#include <conio.h>
#define MAX_NODES 1024         /* 最大ノード数 */
#define INFINITY  1000000000   /* 無限大 */

// ノードを設定する。

#define TOKYO					0		/* 東京 */
#define YURAKUCHO				1		/* 有楽町 */ 
#define SHINBASHI				2		/* 新橋 */
#define HAMAMATSUCHO			3		/* 浜松町 */
#define TAMACHI					4		/* 田町 */
#define SHINAGAWA				5		/* 品川 */
#define OSAKI					6		/* 大崎 */
#define GOTANDA					7		/* 五反田 */
#define MEGURO					8		/* 目黒 */
#define EBISU					9		/* 恵比寿 */
#define SHIBUYA					10		/* 渋谷 */
#define HARAJUKU				11		/* 原宿 */
#define YOYOGI					12		/* 代々木 */
#define SHINJUKU				13		/* 新宿 */
#define SHINOKUBO				14		/* 新大久保 */
#define TAKADANOBABA	    	15		/* 高田馬場 */
#define MEJIRO					16		/* 目白 */
#define IKEBUKURO				17		/* 池袋 */
#define OTSUKA					18		/* 大塚 */
#define SUGAMO					19		/* 巣鴨 */
#define KOMAGOME				20		/* 駒込 */
#define TABATA					21		/* 田端 */
#define NISHINIPPORI	    	22		/* 西日暮里 */
#define NIPPORI					23		/* 日暮里 */
#define UGUISUDANI				24		/* 鴬谷 */
#define UENO					25		/* 上野 */
#define OKACHIMACHI				26		/* 御徒町 */
#define AKIHABARA				27		/* 秋葉原 */
#define KANDA					28		/* 神田 */
#define SENDAGAYA               29      /* 千駄ヶ谷 */
#define SHINANOMACHI            30      /* 信濃町 */
#define YOTSUYA                 31      /* 四ツ谷 */
#define ICHIGAYA                32      /* 市ヶ谷 */
#define IDABASHI                33      /* 飯田橋 */ 
#define SUIDOBASHI              34      /* 水道橋 */
#define OCHANOMIZU              35      /* 御茶ノ水 */
#define OMOTESANDO              36      /* 表参道 */
#define GAIENMAE                37      /* 外苑前 */
#define AOYAMAICCHOME           38      /* 青山一丁目 */
#define AKASAKAMITSUKE          39      /* 赤坂見附 */
#define TAMEIKESANNO            40      /* 溜池山王 */
#define TORANOMON               41      /* 虎ノ門 */
#define SUEHIROCHO              42      /* 末広町 */
#define UENOHIROKOJI            43      /* 上野広小路 */
#define MEIJIJINGUMAE           44      /* 明治神宮前 */
#define NOGIZAKA                45      /* 乃木坂 */
#define AKASAKA                 46      /* 赤坂 */
#define KOKKAIGIJIDOMAE         47      /* 国会議事堂前 */
#define KASUMIGASEKI            48      /* 霞が関 */
#define HIBIYA                  49      /* 日比谷 */
#define NIJUBASHIMAE            50      /* 二重橋前 */
#define OTEMACHI                51      /* 大手町 */
#define SHINOCHANOMIZU          52      /* 新御茶ノ水 */
#define YUSHIMA                 53      /* 湯島 */
#define NEZU                    54      /* 根津 */
#define SENDAGI                 55      /* 千駄木 */
#define HIGASHIIKEBUKURO        56      /* 東池袋 */
#define GOKOKUJI                57      /* 護国寺*/
#define EDOGAWABASHI            58      /* 江戸川橋 */
#define KOJIMACHI               59      /* 麹町 */
#define NAGATACHO               60      /* 永田町 */
#define SAKURADAMON             61      /* 桜田門 */
#define SHIROGANEDAI            62      /* 白金台 */
#define SHIROGANETAKANAWA       63      /* 白金高輪 */
#define MITA                    64      /* 三田 */
#define SHIBAKOEN               65      /* 芝公園 */
#define ONARIMON                66      /* 御成門 */
#define UCHISAIWAICHO           67      /* 内幸町 */
#define JINBOCHO                68      /* 神保町 */
#define KASUGA                  69      /* 春日 */
#define HAKUSAN                 70      /* 白山 */
#define SENGOKU                 71      /* 千石 */
#define AZABUJUBAN              72      /* 麻布十番 */
#define ROPPONGIICCHOME         73      /* 六本木一丁目 */
#define KORAKUEN                74      /* 後楽園 */
#define TODAIMAE                75      /* 東大前 */
#define HONKOMAGOME             76      /* 本駒込 */
#define NISHIGAHARA             77      /* 西ヶ原*/
#define OHJI                    78      /* 王子 */
#define SHINOTSUKA              79      /* 新大塚 */
#define MYOGADANI               80      /* 茗荷谷駅 */
#define HONGOSANCHOME           81      /* 本郷三丁目 */
#define AWAJIMACHI              82      /* 淡路町 */
#define YOTSUYASANCHOME         83      /* 四ツ谷三丁目 */
#define SHINJUKUGYOENMAE        84      /* 新宿御苑前 */
#define SHINJUKUSANCHOME        85      /* 新宿三丁目 */
#define HIROO                   86      /* 広尾 */
#define ROPPONGI                87      /* 六本木 */
#define WASEDA                  88      /* 早稲田 */
#define KAGURAZAKA              89      /* 神楽坂 */
#define KUDANSHITA              90      /* 九段下 */
#define TAKEBASHI               91      /* 竹橋 */
#define HANZOMON                92      /* 半蔵門 */
#define TAKANAWADAI             93      /* 高輪台 */
#define SENGAKUJI               94      /* 泉岳寺 */
#define DAIMON                  95      /* 大門 */
#define AKEBONOBASHI            96      /* 曙橋 */
#define OGAWAMACHI              97      /* 小川町 */
#define KOKURITSUKYOGIJO        98      /* 国立競技場 */
#define AKABANEBASHI            99      /* 赤羽橋 */
#define HIGASHISHINJUKU        100      /* 東新宿 */
#define WAKAMATSUKAWADA        101      /* 若松河田 */
#define USHIGOMEYANAGICHO      102      /* 牛込柳町 */
#define USHIGOMEKAGURAZAKA     103      /* 牛込神楽坂 */

int n=104;  /* ノードの数 */
int time[MAX_NODES][MAX_NODES]; /* time[i][j]はiからjへの所要時間を表す */

void shortest_path(int s, int t, int path[])
{
  struct state {
    int predecessor;  /* 前ノード */
    int length;       /* 探索開始点からの重み */
    enum {permanent,tentative} label;  /* 状態ラベル */
  } state[MAX_NODES];

  int i,k,min;

  struct state *p;

  for(p=&state[0]; p<&state[n]; p++){  /* 構造体stateのメンバの初期化 */
    p -> predecessor = -1;
    p -> length = INFINITY;
    p -> label = tentative;
  }

  state[t].length = 0;
  state[t].label  = permanent;
  k = t; /* k は現在の作業中ノード */

  do{
    for(i=0;i<n;i++){
      if(time[k][i] != 0 && state[i].label == tentative){
	if(state[k].length + time[k][i] < state[i].length){
	  state[i].predecessor = k;
	  state[i].length = state[k].length + time[k][i];
	}
      }
    }

    /* 最短のノードを確定する */
    k = 0;
    min = INFINITY;

    for(i=0;i<n;i++){
      if(state[i].label == tentative && state[i].length < min){
	min = state[i].length;
	k=i;
      }
    }

    state[k].label = permanent;

  } while (k!=s);

  /* 途中経路を配列pathにコピーする */
  i=0;
  k=s;
  do{
    path[i++] = k;
    k = state[k].predecessor;
  } while (k>=0);

}

int main(void)
{
  /* 駅間の経路を所要時間で重み付けする。  */

   /* [  0] 東京駅 */
   time[TOKYO][YURAKUCHO]                = 2;
   time[TOKYO][KANDA]                    = 2;
   /* [  1] 有楽町駅 */
   time[YURAKUCHO][TOKYO]                = 2;
   time[YURAKUCHO][SHINBASHI]            = 2;
   time[YURAKUCHO][SAKURADAMON]          = 2;
   /* [  2] 新橋駅 */
   time[SHINBASHI][YURAKUCHO]            = 2;
   time[SHINBASHI][HAMAMATSUCHO]         = 2;
   time[SHINBASHI][TORANOMON]            = 2;
   time[SHINBASHI][DAIMON]               = 2;
   /* [  3] 浜松町駅 */
   time[HAMAMATSUCHO][SHINBASHI]         = 2;
   time[HAMAMATSUCHO][TAMACHI]           = 3;
   /* [  4] 田町駅 */
   time[TAMACHI][HAMAMATSUCHO]           = 2;
   time[TAMACHI][SHINAGAWA]              = 2;
   /* [  5] 品川駅 */
   time[SHINAGAWA][TAMACHI]              = 2;
   time[SHINAGAWA][OSAKI]                = 4;
   /* [  6] 大崎駅 */
   time[OSAKI][SHINAGAWA]                = 4;
   time[OSAKI][GOTANDA]                  = 1;
   /* [  7] 五反田駅 */
   time[GOTANDA][OSAKI]                  = 1;
   time[GOTANDA][MEGURO]                 = 2;
   time[GOTANDA][TAKANAWADAI]            = 2;
   /* [  8] 目黒駅 */
   time[MEGURO][GOTANDA]                 = 2;
   time[MEGURO][EBISU]                   = 3;
   time[MEGURO][SHIROGANEDAI]            = 2;
   /* [  9] 恵比寿駅 */
   time[EBISU][MEGURO]                   = 3;
   time[EBISU][SHIBUYA]                  = 2;
   time[EBISU][HIROO]                    = 3;
   /* [ 10] 渋谷駅 */
   time[SHIBUYA][EBISU]                  = 2;
   time[SHIBUYA][HARAJUKU]               = 2;
   time[SHIBUYA][OMOTESANDO]             = 3;
   /* [ 11] 原宿駅 */
   time[HARAJUKU][SHIBUYA]               = 2;
   time[HARAJUKU][YOYOGI]                = 3;
   /* [ 12] 代々木駅 */
   time[YOYOGI][HARAJUKU]                = 3;
   time[YOYOGI][SHINJUKU]                = 1;
   time[YOYOGI][KOKURITSUKYOGIJO]        = 3;
   /* [ 13] 新宿駅 */
   time[SHINJUKU][YOYOGI]                = 1;
   time[SHINJUKU][SHINOKUBO]             = 2;
   time[SHINJUKU][SHINJUKUSANCHOME]      = 1;
   /* [ 14] 新大久保駅 */
   time[SHINOKUBO][SHINJUKU]             = 2;
   time[SHINOKUBO][TAKADANOBABA]         = 1;
   /* [ 15] 高田馬場駅 */
   time[TAKADANOBABA][SHINOKUBO]         = 1;
   time[TAKADANOBABA][MEJIRO]            = 2;
   time[TAKADANOBABA][WASEDA]            = 4;
   /* [ 16] 目白駅 */
   time[MEJIRO][TAKADANOBABA]            = 2;
   time[MEJIRO][IKEBUKURO]               = 3;
   /* [ 17] 池袋駅 */
   time[IKEBUKURO][MEJIRO]               = 3;
   time[IKEBUKURO][OTSUKA]               = 2;
   time[IKEBUKURO][HIGASHIIKEBUKURO]     = 2;
   time[IKEBUKURO][SHINOTSUKA]           = 4;
   /* [ 18] 大塚駅 */
   time[OTSUKA][IKEBUKURO]               = 2;
   time[OTSUKA][SUGAMO]                  = 2;
   /* [ 19] 巣鴨駅 */
   time[SUGAMO][OTSUKA]                  = 2;
   time[SUGAMO][KOMAGOME]                = 2;
   time[SUGAMO][SENGOKU]                 = 2;
   /* [ 20] 駒込駅 */
   time[KOMAGOME][SUGAMO]                = 2;
   time[KOMAGOME][TABATA]                = 2;
   time[KOMAGOME][HONKOMAGOME]           = 2;
   time[KOMAGOME][NISHIGAHARA]           = 2;
   /* [ 21] 田端駅 */
   time[TABATA][KOMAGOME]                = 2;
   time[TABATA][NISHINIPPORI]            = 2;
   /* [ 22] 西日暮里駅 */
   time[NISHINIPPORI][TABATA]            = 2;
   time[NISHINIPPORI][NIPPORI]           = 2;
   time[NISHINIPPORI][SENDAGI]           = 2;
   /* [ 23] 日暮里駅 */
   time[NIPPORI][NISHINIPPORI]           = 2;
   time[NIPPORI][UGUISUDANI]             = 2;
   /* [ 24] 鴬谷駅 */
   time[UGUISUDANI][NIPPORI]             = 2;
   time[UGUISUDANI][UENO]                = 3;
   /* [ 25] 上野駅 */
   time[UENO][UGUISUDANI]                = 3;
   time[UENO][OKACHIMACHI]               = 2;
   time[UENO][UENOHIROKOJI]              = 2;
   /* [ 26] 御徒町駅 */
   time[OKACHIMACHI][UENO]               = 2;
   time[OKACHIMACHI][AKIHABARA]          = 2;
   /* [ 27] 秋葉原駅 */
   time[AKIHABARA][OKACHIMACHI]          = 2;
   time[AKIHABARA][KANDA]                = 2;
   time[AKIHABARA][OCHANOMIZU]           = 2;
   /* [ 28] 神田駅 */
   time[KANDA][AKIHABARA]                = 2;
   time[KANDA][TOKYO]                    = 2;
   time[KANDA][OCHANOMIZU]               = 2;
   time[KANDA][SUEHIROCHO]               = 2;
   /* [ 29] 千駄ヶ谷駅 */
   time[SENDAGAYA][YOYOGI]               = 1;
   time[SENDAGAYA][SHINANOMACHI]         = 1;
   /* [ 30] 信濃町駅 */
   time[SHINANOMACHI][SENDAGAYA]         = 1;
   time[SHINANOMACHI][YOTSUYA]           = 2;
   /* [ 31] 四ツ谷駅 */
   time[YOTSUYA][SHINANOMACHI]           = 2;
   time[YOTSUYA][ICHIGAYA]               = 2;
   time[YOTSUYA][YOTSUYASANCHOME]        = 2;
   /* [ 32] 市ヶ谷駅 */
   time[ICHIGAYA][YOTSUYA]               = 2;
   time[ICHIGAYA][IDABASHI]              = 2;
   time[ICHIGAYA][KOJIMACHI]             = 2;
   time[ICHIGAYA][AKEBONOBASHI]          = 1;
   /* [ 33] 飯田橋駅 */
   time[IDABASHI][ICHIGAYA]              = 2;
   time[IDABASHI][SUIDOBASHI]            = 2;
   time[IDABASHI][EDOGAWABASHI]          = 3;
   time[IDABASHI][KORAKUEN]              = 2;
   time[IDABASHI][KAGURAZAKA]            = 2;
   time[IDABASHI][KUDANSHITA]            = 2;
   time[IDABASHI][USHIGOMEKAGURAZAKA]    = 3;
   /* [ 34] 水道橋駅 */
   time[SUIDOBASHI][IDABASHI]            = 2;
   time[SUIDOBASHI][OCHANOMIZU]          = 2;
   time[SUIDOBASHI][JINBOCHO]            = 2;
   time[SUIDOBASHI][KASUGA]              = 2;
   /* [ 35] 御茶ノ水駅 */
   time[OCHANOMIZU][SUIDOBASHI]          = 2;
   time[OCHANOMIZU][AKIHABARA]           = 2;
   time[OCHANOMIZU][KANDA]               = 2;
   time[OCHANOMIZU][HONGOSANCHOME]       = 2;
   time[OCHANOMIZU][AWAJIMACHI]          = 2;
   /* [ 36] 表参道駅 */
   time[OMOTESANDO][SHIBUYA]             = 3;
   time[OMOTESANDO][GAIENMAE]            = 1;
   time[OMOTESANDO][MEIJIJINGUMAE]       = 1;
   time[OMOTESANDO][NOGIZAKA]            = 3;
   /* [ 37] 外苑前駅*/
   time[GAIENMAE][OMOTESANDO]            = 1;
   time[GAIENMAE][AOYAMAICCHOME]         = 2;
   /* [ 38] 青山一丁目駅 */
   time[AOYAMAICCHOME][GAIENMAE]         = 2;
   time[AOYAMAICCHOME][AKASAKAMITSUKE]   = 2;
   time[AOYAMAICCHOME][KOKURITSUKYOGIJO] = 2;
   /* [ 39] 赤坂見附駅 */
   time[AKASAKAMITSUKE][AOYAMAICCHOME]   = 2;
   time[AKASAKAMITSUKE][TAMEIKESANNO]    = 2;
   /* [ 40] 溜池山王駅 */
   time[TAMEIKESANNO][AKASAKAMITSUKE]    = 2;
   time[TAMEIKESANNO][TORANOMON]         = 2;
   time[TAMEIKESANNO][ROPPONGIICCHOME]   = 2;
   /* [ 41] 虎ノ門駅 */
   time[TORANOMON][TAMEIKESANNO]         = 2;
   time[TORANOMON][SHINBASHI]            = 2;
   /* [ 42] 末広町*/
   time[SUEHIROCHO][KANDA]               = 2;
   time[SUEHIROCHO][UENOHIROKOJI]        = 1;
   /* [ 43] 上野広小路駅 */
   time[UENOHIROKOJI][SUEHIROCHO]        = 1;
   time[UENOHIROKOJI][UENO]              = 2;
   /* [ 44] 明治神宮前駅 */
   time[MEIJIJINGUMAE][OMOTESANDO]       = 1;
   /* [ 45] 乃木坂駅 */
   time[NOGIZAKA][OMOTESANDO]            = 3;
   time[NOGIZAKA][AKASAKA]               = 2;
   /* [ 46] 赤坂駅 */
   time[AKASAKA][NOGIZAKA]               = 2;
   time[AKASAKA][KOKKAIGIJIDOMAE]        = 1;
   /* [ 47] 国会議事堂前駅 */
   time[KOKKAIGIJIDOMAE][AKASAKA]        = 1;
   time[KOKKAIGIJIDOMAE][KASUMIGASEKI]   = 2;
   /* [ 48] 霞ヶ関駅 */
   time[KASUMIGASEKI][KOKKAIGIJIDOMAE]   = 2;
   time[KASUMIGASEKI][HIBIYA]            = 2;
   /* [ 49] 日比谷駅 */
   time[HIBIYA][KASUMIGASEKI]            = 2;
   time[HIBIYA][NIJUBASHIMAE]            = 2;
   time[HIBIYA][UCHISAIWAICHO]           = 1;
   /* [ 50] 二重橋前 */
   time[NIJUBASHIMAE][HIBIYA]            = 2;
   time[NIJUBASHIMAE][OTEMACHI]          = 1;
   /* [ 51] 大手町駅 */
   time[OTEMACHI][NIJUBASHIMAE]          = 1;
   time[OTEMACHI][SHINOCHANOMIZU]        = 2;
   time[OTEMACHI][JINBOCHO]              = 3;
   time[OTEMACHI][AWAJIMACHI]            = 1;
   time[OTEMACHI][TAKEBASHI]             = 2;
   /* [ 52] 新御茶ノ水駅 */
   time[SHINOCHANOMIZU][OTEMACHI]        = 2;
   time[SHINOCHANOMIZU][YUSHIMA]         = 3;
   /* [ 53] 湯島駅 */
   time[YUSHIMA][SHINOCHANOMIZU]         = 3;
   time[YUSHIMA][NEZU]                   = 2;
   /* [ 54] 根津駅 */
   time[NEZU][YUSHIMA]                   = 2;
   time[NEZU][SENDAGI]                   = 2;
   /* [ 55] 千駄木駅 */
   time[SENDAGI][NEZU]                   = 2;
   time[SENDAGI][NISHINIPPORI]           = 2;
   /* [ 56] 東池袋駅 */
   time[HIGASHIIKEBUKURO][IKEBUKURO]     = 2;
   time[HIGASHIIKEBUKURO][GOKOKUJI]      = 2;
   /* [ 57] 護国寺駅 */
   time[GOKOKUJI][HIGASHIIKEBUKURO]      = 2;
   time[GOKOKUJI][EDOGAWABASHI]          = 3;
   /* [ 58] 江戸川橋駅 */
   time[EDOGAWABASHI][GOKOKUJI]          = 3;
   time[EDOGAWABASHI][IDABASHI]          = 3;
   /* [ 59] 麹町駅 */
   time[KOJIMACHI][ICHIGAYA]             = 2;
   time[KOJIMACHI][NAGATACHO]            = 1;
   /* [ 60] 永田町駅 */
   time[NAGATACHO][KOJIMACHI]            = 1;
   time[NAGATACHO][SAKURADAMON]          = 2;
   time[NAGATACHO][HANZOMON]             = 2;
   /* [ 61] 桜田門駅 */
   time[SAKURADAMON][NAGATACHO]          = 2;
   time[SAKURADAMON][YURAKUCHO]          = 2;
   /* [ 62] 白金台駅 */
   time[SHIROGANEDAI][MEGURO]            = 2;
   time[SHIROGANEDAI][SHIROGANETAKANAWA] = 2;
   /* [ 63] 白金高輪駅 */
   time[SHIROGANETAKANAWA][SHIROGANEDAI] = 2;
   time[SHIROGANETAKANAWA][SHIBAKOEN]    = 2;
   time[SHIROGANETAKANAWA][AZABUJUBAN]   = 3;
   /* [ 64] 芝公園駅 */
   time[SHIBAKOEN][SHIROGANETAKANAWA]    = 2;
   time[SHIBAKOEN][MITA]                 = 2;
   /* [ 65] 三田駅 */
   time[MITA][SHIBAKOEN]                 = 2;
   time[MITA][ONARIMON]                  = 2;
   time[MITA][SENGAKUJI]                 = 2;
   time[MITA][DAIMON]                    = 2;
   /* [ 66] 御成門駅 */
   time[ONARIMON][MITA]                  = 2;
   time[ONARIMON][UCHISAIWAICHO]         = 2;
   /* [ 67] 内幸町駅 */
   time[UCHISAIWAICHO][ONARIMON]         = 2;
   time[UCHISAIWAICHO][HIBIYA]           = 1;
   /* [ 68] 神保町 */
   time[JINBOCHO][OTEMACHI]              = 3;
   time[JINBOCHO][SUIDOBASHI]            = 2;
   time[JINBOCHO][ROPPONGI]              = 3;
   time[JINBOCHO][OGAWAMACHI]            = 5;
   /* [ 69] 春日駅 */
   time[KASUGA][SUIDOBASHI]              = 2;
   time[KASUGA][HAKUSAN]                 = 2;
   /* [ 70] 白山駅*/
   time[HAKUSAN][KASUGA]                 = 2;
   time[HAKUSAN][SENGOKU]                = 2;
   /* [ 71] 千石駅 */
   time[SENGOKU][HAKUSAN]                = 2;
   time[SENGOKU][SUGAMO]                 = 2;
   /* [ 72] 麻布十番駅 */
   time[AZABUJUBAN][SHIROGANETAKANAWA]   = 3;
   time[AZABUJUBAN][ROPPONGIICCHOME]     = 2;
   time[AZABUJUBAN][AKABANEBASHI]        = 2;
   /* [ 73] 六本木一丁目駅 */
   time[ROPPONGIICCHOME][AZABUJUBAN]     = 2;
   time[ROPPONGIICCHOME][TAMEIKESANNO]   = 2;
   /* [ 74] 後楽園駅 */
   time[KORAKUEN][IDABASHI]              = 2;
   time[KORAKUEN][TODAIMAE]              = 3;
   time[KORAKUEN][MYOGADANI]             = 2;
   time[KORAKUEN][HONGOSANCHOME]         = 2;
   /* [ 75] 東大前駅 */
   time[TODAIMAE][KORAKUEN]              = 3;
   time[TODAIMAE][HONKOMAGOME]           = 2;
   /* [ 76] 本駒込駅 */
   time[HONKOMAGOME][TODAIMAE]           = 2;
   time[HONKOMAGOME][KOMAGOME]           = 2;
   /* [ 77] 西ヶ原駅*/
   time[NISHIGAHARA][KOMAGOME]           = 2;
   time[NISHIGAHARA][OHJI]               = 2;
   /* [ 78] 王子駅 */
   time[OHJI][NISHIGAHARA]               = 2;
   /* [ 79] 新大塚駅 */
   time[SHINOTSUKA][IKEBUKURO]           = 4;
   time[SHINOTSUKA][MYOGADANI]           = 2;
   /* [ 80] 茗荷谷駅 */
   time[MYOGADANI][SHINOTSUKA]           = 2;
   time[MYOGADANI][KORAKUEN]             = 2;
   /* [ 81] 本郷三丁目駅 */
   time[HONGOSANCHOME][KORAKUEN]         = 2;
   time[HONGOSANCHOME][SHINOCHANOMIZU]   = 2;
   /* [ 82] 淡路町駅 */
   time[AWAJIMACHI][SHINOCHANOMIZU]      = 2;
   time[AWAJIMACHI][OTEMACHI]            = 1;
   /* [ 83] 四ツ谷三丁目駅 */
   time[YOTSUYASANCHOME][YOTSUYA]           = 2;
   time[YOTSUYASANCHOME][SHINJUKUGYOENMAE]  = 2;
   /* [ 84] 新宿御苑前駅 */
   time[SHINJUKUGYOENMAE][YOTSUYASANCHOME]  = 2;
   time[SHINJUKUGYOENMAE][SHINJUKUSANCHOME] = 2;
   /* [ 85] 新宿三丁目駅 */
   time[SHINJUKUSANCHOME][SHINJUKUGYOENMAE] = 2;
   time[SHINJUKUSANCHOME][SHINJUKU]         = 1;
   time[SHINJUKUSANCHOME][AKEBONOBASHI]     = 2;
   /* [ 86] 広尾駅 */
   time[HIROO][EBISU]                    = 3;
   time[HIROO][ROPPONGI]                 = 3;
   /* [ 87] 六本木駅 */
   time[ROPPONGI][HIROO]                 = 3;
   time[ROPPONGI][JINBOCHO]              = 3;
   /* [ 88] 早稲田駅 */
   time[WASEDA][TAKADANOBABA]            = 4;
   time[WASEDA][KAGURAZAKA]              = 2;
   /* [ 89] 神楽坂駅 */
   time[KAGURAZAKA][WASEDA]              = 2;
   time[KAGURAZAKA][IDABASHI]            = 2;
   /* [ 90] 九段下駅 */
   time[KUDANSHITA][IDABASHI]            = 2;
   time[KUDANSHITA][TAKEBASHI]           = 2;
   time[KUDANSHITA][HANZOMON]            = 3;
   /* [ 91] 竹橋駅 */
   time[TAKEBASHI][KUDANSHITA]           = 2;
   time[TAKEBASHI][OTEMACHI]             = 2;
   /* [ 92] 半蔵門駅 */
   time[HANZOMON][NAGATACHO]             = 2;
   time[HANZOMON][KUDANSHITA]            = 3;
   /* [ 93] 高輪台駅 */
   time[TAKANAWADAI][GOTANDA]            = 2;
   time[TAKANAWADAI][SENGAKUJI]          = 3;
   /* [ 94] 泉岳寺駅 */
   time[SENGAKUJI][TAKANAWADAI]          = 3;
   time[SENGAKUJI][MITA]                 = 2;
   /* [ 95] 大門駅 */
   time[DAIMON][MITA]                    = 2;
   time[DAIMON][SHINBASHI]               = 2;
   time[DAIMON][AKABANEBASHI]            = 3;
   /* [ 96] 曙橋駅 */
   time[AKEBONOBASHI][SHINJUKUSANCHOME]  = 2;
   time[AKEBONOBASHI][ICHIGAYA]          = 1;
   /* [ 97] 小川町駅 */
   time[OGAWAMACHI][JINBOCHO]            = 5;
   /* [ 98] 国立競技場駅 */
   time[KOKURITSUKYOGIJO][YOYOGI]        = 3;
   time[KOKURITSUKYOGIJO][AOYAMAICCHOME] = 2;
   /* [ 99] 赤羽橋駅 */
   time[AKABANEBASHI][AZABUJUBAN]        = 2;
   time[AKABANEBASHI][DAIMON]            = 3;
   /* [100] 東新宿駅 */
   time[HIGASHISHINJUKU][WAKAMATSUKAWADA] = 2;
   /* [101] 若松河田 */
   time[WAKAMATSUKAWADA][HIGASHISHINJUKU]        = 2;
   time[WAKAMATSUKAWADA][USHIGOMEYANAGICHO]      = 2;
   /* [102] 牛込柳町 */
   time[USHIGOMEYANAGICHO][WAKAMATSUKAWADA]      = 2;
   time[USHIGOMEYANAGICHO][USHIGOMEKAGURAZAKA]   = 2;
   /* [103] 牛込神楽坂 */
   time[USHIGOMEKAGURAZAKA][USHIGOMEYANAGICHO]   = 2;
   time[USHIGOMEKAGURAZAKA][IDABASHI]            = 3;
   
   


                            // 駅番号 /  駅名 //
   char station[104][20] = { /*   0 */ "東京",     
							 /*   1 */ "有楽町",    
							 /*   2 */ "新橋",      
						     /*   3 */ "浜松町",    
						     /*   4 */ "田町",
						     /*   5 */ "品川",
						     /*   6 */ "大崎",
						     /*   7 */ "五反田",
						     /*   8 */ "目黒",
						     /*   9 */ "恵比寿",
						     /*  10 */ "渋谷",
						     /*  11 */ "原宿",
						     /*  12 */ "代々木",
						     /*  13 */ "新宿",
						     /*  14 */ "新大久保",
						     /*  15 */ "高田馬場",
						     /*  16 */ "目白",
						     /*  17 */ "池袋",
						     /*  18 */ "大塚",
				  		     /*  19 */ "巣鴨",
						     /*  20 */ "駒込",
						     /*  21 */ "田端",
						     /*  22 */ "西日暮里",
							 /*  23 */ "日暮里",
							 /*  24 */ "鴬谷",
							 /*  25 */ "上野",
							 /*  26 */ "御徒町",
							 /*  27 */ "秋葉原",
							 /*  28 */ "神田",
							 /*  29 */ "千駄ヶ谷",
							 /*  30 */ "信濃町",
							 /*  31 */ "四ツ谷",
							 /*  32 */ "市ヶ谷",
							 /*  33 */ "飯田橋",
							 /*  34 */ "水道橋",
							 /*  35 */ "御茶ノ水",
							 /*  36 */ "表\参道",
							 /*  37 */ "外苑前",
							 /*  38 */ "青山一丁目",
							 /*  39 */ "赤坂見附",
							 /*  40 */ "溜池山王",
							 /*  41 */ "虎ノ門",
							 /*  42 */ "末広町",
							 /*  43 */ "上野広小路",
							 /*  44 */ "明治神宮前",
							 /*  45 */ "乃木坂",
							 /*  46 */ "赤坂",
							 /*  47 */ "国会議事堂前",
							 /*  48 */ "霞が関",
							 /*  49 */ "日比谷",
							 /*  50 */ "二重橋前",
							 /*  51 */ "大手町",
							 /*  52 */ "新御茶ノ水",
							 /*  53 */ "湯島",
							 /*  54 */ "根津",
							 /*  55 */ "千駄木",
							 /*  56 */ "東池袋",
							 /*  57 */ "護国寺",
							 /*  58 */ "江戸川橋",
							 /*  59 */ "麹町",
							 /*  60 */ "永田町",
							 /*  61 */ "桜田門",
							 /*  62 */ "白金台",
							 /*  63 */ "白金高輪",
							 /*  64 */ "三田",
							 /*  65 */ "芝公園",
							 /*  66 */ "御成門",
							 /*  67 */ "内幸町",
							 /*  68 */ "神保町",
							 /*  69 */ "春日",
							 /*  70 */ "白山",
							 /*  71 */ "千石",
							 /*  72 */ "麻布十\番",
							 /*  73 */ "六本木一丁目",
							 /*  74 */ "後楽園",
							 /*  75 */ "東大前",
							 /*  76 */ "本駒込",
							 /*  77 */ "西ヶ原",
							 /*  78 */ "王子",
							 /*  79 */ "新大塚",
							 /*  80 */ "茗荷谷",
							 /*  81 */ "本郷三丁目",
							 /*  82 */ "淡路町",
							 /*  83 */ "四ツ谷三丁目",
							 /*  84 */ "新宿御苑前",
							 /*  85 */ "新宿三丁目",
							 /*  86 */ "広尾",
							 /*  87 */ "六本木",
							 /*  88 */ "早稲田",
							 /*  89 */ "神楽坂",
							 /*  90 */ "九段下",
							 /*  91 */ "竹橋",
							 /*  92 */ "半蔵門",
							 /*  93 */ "高輪台",
							 /*  94 */ "泉岳寺",
							 /*  95 */ "大門",
							 /*  96 */ "曙橋",
							 /*  97 */ "小川町",
							 /*  98 */ "国立競技場",
							 /*  99 */ "赤羽橋",
							 /* 100 */ "東新宿",
							 /* 101 */ "若松河田",
							 /* 102 */ "牛込柳町",
							 /* 103 */ "牛込神楽坂"
   };

   int s_line;    // 出発駅のある路線
   int t_line;    // 到着駅のある路線
   int s;         // 出発駅
   int t;         // 到着駅
   int path[104]; // 途中経路記録用配列
   int i;         // ループ用作業変数
   char a[30];    // 終了表示用

   printf("山手線内部駅間の最短所要時間経路を探索します。\n");
   printf("============================================================================\n");

   printf("[ 0]山手線   [ 1]中央線   [ 2]銀座線   [ 3]千代田線   [ 4]有楽町線\n");
   printf("[ 5]都営三田線 [ 6]南北線   [ 7]丸の内線  [ 8]日比谷線   [ 9]東西線\n");
   printf("[10]半蔵門線  [11]浅草線   [12]新宿線   [13]大江戸線\n");
   printf("----------------------------------------------------------------------------\n");
   printf("出発駅のある路線を選択してください:"); scanf("%d",&s_line);

   putchar('\n');

   switch (s_line) {
     // 山手線
   case 0 : 
     printf("[ 0]東京駅   [ 1]有楽町駅 [ 2]新橋駅   [ 3]浜松町駅 [ 4]田町駅\n");
     printf("[ 5]品川駅   [ 6]大崎駅  [ 7]五反田駅  [ 8]目黒駅  [ 9]恵比寿駅\n");
     printf("[10]渋谷駅   [11]原宿駅  [12]代々木駅  [13]新宿駅  [14]新大久保駅\n");
     printf("[15]高田馬場駅 [16]目白駅  [17]池袋駅   [18]大塚駅  [19]巣鴨駅\n");
     printf("[20]駒込駅   [21]田端駅  [22]西日暮里駅 [23]日暮里駅 [24]鴬谷駅\n");
     printf("[25]上野駅   [26]御徒町駅 [27]秋葉原駅  [28]神田駅\n");

     break;
 
     // 中央線
   case 1 :
     printf("[29]千駄ヶ谷駅 [30]信濃町駅 [31]四ツ谷駅 [32]市ヶ谷駅 [33]飯田橋駅\n");
     printf("[34]水道橋駅  [35]御茶ノ水駅\n");

     break;

     // 銀座線
   case 2 : 
     printf("銀座-浅草は山手線外なので選択できません。\n");
     printf("[10]渋谷駅    [36]表\参道駅 [37]外苑前駅 [38]青山一丁目駅 [39]赤坂見附駅\n");
     printf("[40]溜池山王駅  [41]虎ノ門駅 [ 2]新橋駅  [28]神田駅    [42]末広町駅\n");
     printf("[44]上野広小路駅 [25]上野駅\n");

     break;

     // 千代田線
   case 3 :
     printf("代々木上原-北綾瀬は山手線外なので選択できません。\n");

     printf("[44]明治神宮前 [45]乃木坂駅  [46]赤坂駅  [47]国会議事堂前駅 [48]霞ヶ関駅\n");
     printf("[49]日比谷駅  [50]二重橋前駅 [51]大手町駅 [52]新御茶ノ水駅  [53]湯島駅\n");
     printf("[54]根津駅   [55]千駄木駅\n");

     break;

     // 有楽町線
   case 4 :
     printf("和光市-新木場山手線外の駅なので選択できません。\n");

     printf("[17]池袋駅  [56]東池袋駅 [57]護国寺駅 [58]江戸川橋駅 [59]麹町\n");
     printf("[60]永田町駅 [61]桜田門駅\n");

     break;

     // 三田線
   case 5 :
     printf("西巣鴨-西高島平間は山手線外の駅なので選択できません。\n");

     printf("[ 8]目黒駅  [62]白金台駅 [63]白金高輪駅 [64]三田駅 [65]芝公園駅\n");
     printf("[66]御成門駅 [67]内幸町駅 [68]神保町駅  [69]春日駅 [70]白山駅\n");
     printf("[71]千石駅  [19]巣鴨駅\n");

     break;

     // 南北線
   case 6 :
     printf("王子神谷-赤羽岩淵は山手線外なので選択できません。\n");
     
     printf("[ 8]目黒駅   [62]白金台駅 [63]白金高輪駅 [72]麻布十\番駅 [73]六本木一丁目駅\n");
     printf("[40]溜池山王駅 [60]永田町駅 [31]四ツ谷駅  [32]市ヶ谷駅  [33]飯田橋駅\n");
     printf("[74]後楽園駅  [75]東大前駅 [76]本駒込駅  [20]駒込    [77]西ヶ原駅\n");
     printf("[78]王子駅\n");

     break;

     // 丸ノ内線
   case 7 :
     printf("銀座-方南町は山手線外なので選択できません。\n");

     printf("[17]池袋駅     [79]新大塚駅  [80]茗荷谷駅 [74]後楽園駅    [81]本郷三丁目駅\n");
     printf("[35]御茶ノ水駅   [82]淡路町駅  [51]大手町駅 [ 0]東京駅     [48]霞ヶ関駅\n");
     printf("[47]国会議事堂前駅 [39]赤坂見附駅 [31]四ツ谷駅 [83]四ツ谷三丁目駅 [84]新宿御苑前駅\n");
     printf("[85]新宿三丁目駅  [13]新宿駅\n");

     break;

     // 日比谷線
   case 8 :
     printf("銀座-北千住間は山手線外の駅なので選択できません。\n");
     
     printf("[ 9]恵比寿駅 [86]広尾駅  [87]六本木駅 [68]神保町駅 [48]霞ヶ関駅\n");
     printf("[49]日比谷駅 [27]秋葉原駅 [25]上野駅\n");
  
     break;
     
     // 東西線
   case 9 :
     printf("日本橋-西船橋間は山手線外のため選択できません。\n");

     printf("[15]高田馬場駅 [88]早稲田駅 [89]神楽坂駅 [33]飯田橋駅 [90]九段下駅\n");
     printf("[91]竹橋駅   [51]大手町駅\n");

     break;

     // 半蔵門線
   case 10 :
     printf("三越前-押髪間は山手線外なので選択できません。\n");

     printf("[10]渋谷駅  [36]表\参道駅 [38]青山一丁目駅 [60]永田町駅 [92]半蔵門駅\n");
     printf("[90]九段下駅 [68]神保町駅  [51]大手町駅\n");
     
     break;

     // 浅草線
   case 11 :
     printf("西馬込-戸越間、東銀座-押上間は山手線外なので選択できません。\n");

     printf("[ 7]五反田駅 [93]高輪台駅 [94]泉岳寺駅 [64]三田駅 [95]大門駅\n");
     printf("[ 2]新橋駅\n");

     break;

     // 新宿線
   case 12 :
     printf("岩本町-本八幡間は山手線外なので選択できません。\n");

     printf("[13]新宿駅  [85]新宿三丁目駅 [96]曙橋駅 [32]市ヶ谷駅 [90]九段下駅\n");
     printf("[68]神保町駅 [97]小川町駅\n");
     
     break;

     // 大江戸線
   case 13 :
     printf("汐留-上野御徒町間、新宿西口-光が丘間は山手線外のため選択できません。\n");

     printf("[ 13]新宿駅   [ 12]代々木駅   [ 98]国立競技場駅 [ 38]青山一丁目駅 [ 87]六本木駅\n");
     printf("[ 72]麻布十\番駅 [ 99]赤羽橋駅   [ 95]大門駅    [100]東新宿駅   [101]若松河田駅\n");
     printf("[102]牛込柳町駅 [103]牛込神楽坂駅 [ 33]飯田橋駅   [ 69]春日駅    [ 81]本郷三丁目駅\n");

     break;

   default:
     return 1;

   }

   printf("----------------------------------------------------------------------------\n"); 
   printf("出発駅を選択してください:"); scanf("%d",&s);

   putchar('\n');

   printf("============================================================================\n");

   printf("[ 0]山手線   [ 1]中央線   [ 2]銀座線   [ 3]千代田線   [ 4]有楽町線\n");
   printf("[ 5]都営三田線 [ 6]南北線   [ 7]丸の内線  [ 8]日比谷線   [ 9]東西線\n");
   printf("[10]半蔵門線  [11]浅草線   [12]新宿線   [13]大江戸線\n");
   printf("----------------------------------------------------------------------------\n");
   printf("到着駅のある路線を選択してください:"); scanf("%d",&t_line);

   putchar('\n');

   switch (t_line) {
     // 山手線
   case 0 : 
     printf("[ 0]東京駅   [ 1]有楽町駅 [ 2]新橋駅   [ 3]浜松町駅 [ 4]田町駅\n");
     printf("[ 5]品川駅   [ 6]大崎駅  [ 7]五反田駅  [ 8]目黒駅  [ 9]恵比寿駅\n");
     printf("[10]渋谷駅   [11]原宿駅  [12]代々木駅  [13]新宿駅  [14]新大久保駅\n");
     printf("[15]高田馬場駅 [16]目白駅  [17]池袋駅   [18]大塚駅  [19]巣鴨駅\n");
     printf("[20]駒込駅   [21]田端駅  [22]西日暮里駅 [23]日暮里駅 [24]鴬谷駅\n");
     printf("[25]上野駅   [26]御徒町駅 [27]秋葉原駅  [28]神田駅\n");

     break;
 
     // 中央線
   case 1 :
     printf("[29]千駄ヶ谷駅 [30]信濃町駅 [31]四ツ谷駅 [32]市ヶ谷駅 [33]飯田橋駅\n");
     printf("[34]水道橋駅  [35]御茶ノ水駅\n");

     break;

     // 銀座線
   case 2 : 
     printf("銀座-浅草は山手線外なので選択できません。\n");

     printf("[10]渋谷駅    [36]表\参道駅 [37]外苑前駅 [38]青山一丁目駅 [39]赤坂見附駅\n");
     printf("[40]溜池山王駅  [41]虎ノ門駅 [ 2]新橋駅  [28]神田駅    [42]末広町駅\n");
     printf("[44]上野広小路駅 [25]上野駅\n");

     break;

     // 千代田線
   case 3 :
     printf("代々木上原-北綾瀬は山手線外なので選択できません。\n");

     printf("[44]明治神宮前 [45]乃木坂駅  [46]赤坂駅  [47]国会議事堂前駅 [48]霞ヶ関駅\n");
     printf("[49]日比谷駅  [50]二重橋前駅 [51]大手町駅 [52]新御茶ノ水駅  [53]湯島駅\n");
     printf("[54]根津駅   [55]千駄木駅\n");

     break;

     // 有楽町線
   case 4 :
     printf("和光市-新木場山手線外の駅なので選択できません。\n");

     printf("[17]池袋駅  [56]東池袋駅 [57]護国寺駅 [58]江戸川橋駅 [59]麹町\n");
     printf("[60]永田町駅 [61]桜田門駅\n");

     break;

     // 三田線
   case 5 :
     printf("西巣鴨-西高島平間は山手線外の駅なので選択できません。\n");

     printf("[ 8]目黒駅  [62]白金台駅 [63]白金高輪駅 [64]三田駅 [65]芝公園駅\n");
     printf("[66]御成門駅 [67]内幸町駅 [68]神保町駅  [69]春日駅 [70]白山駅\n");
     printf("[71]千石駅  [19]巣鴨駅\n");

     break;

     // 南北線
   case 6 :
     printf("王子神谷-赤羽岩淵は山手線外なので選択できません。\n");
     
     printf("[ 8]目黒駅   [62]白金台駅 [63]白金高輪駅 [72]麻布十\番駅 [73]六本木一丁目駅\n");
     printf("[40]溜池山王駅 [60]永田町駅 [31]四ツ谷駅  [32]市ヶ谷駅  [33]飯田橋駅\n");
     printf("[74]後楽園駅  [75]東大前駅 [76]本駒込駅  [20]駒込    [77]西ヶ原駅\n");
     printf("[78]王子駅\n");

     break;

     // 丸ノ内線
   case 7 :
     printf("銀座-方南町は山手線外なので選択できません。\n");

     printf("[17]池袋駅     [79]新大塚駅  [80]茗荷谷駅 [74]後楽園駅    [81]本郷三丁目駅\n");
     printf("[35]御茶ノ水駅   [82]淡路町駅  [51]大手町駅 [ 0]東京駅     [48]霞ヶ関駅\n");
     printf("[47]国会議事堂前駅 [39]赤坂見附駅 [31]四ツ谷駅 [83]四ツ谷三丁目駅 [84]新宿御苑前駅");
     printf("[85]新宿三丁目駅  [13]新宿駅");

     break;

     // 日比谷線
   case 8 :
     printf("銀座-北千住間は山手線外の駅なので選択できません。\n");
     
     printf("[ 9]恵比寿駅 [86]広尾駅  [87]六本木駅 [68]神保町駅 [48]霞ヶ関駅\n");
     printf("[49]日比谷駅 [27]秋葉原駅 [25]上野駅\n");
  
     break;
     
     // 東西線
   case 9 :
     printf("日本橋-西船橋間は山手線外のため選択できません。");

     printf("[15]高田馬場駅 [88]早稲田駅 [89]神楽坂駅 [33]飯田橋駅 [90]九段下駅\n");
     printf("[91]竹橋駅   [51]大手町駅\n");

     break;

     // 半蔵門線
   case 10 :
     printf("三越前-押髪間は山手線外なので選択できません。\n");

     printf("[10]渋谷駅  [36]表\参道駅 [38]青山一丁目駅 [60]永田町駅 [92]半蔵門駅\n");
     printf("[90]九段下駅 [68]神保町駅  [51]大手町駅\n");
     
     break;

     // 浅草線
   case 11 :
     printf("西馬込-戸越間、東銀座-押上間は山手線外なので選択できません。\n");

     printf("[ 7]五反田駅 [93]高輪台駅 [94]泉岳寺駅 [64]三田駅 [95]大門駅\n");
     printf("[ 2]新橋駅\n");

     break;

     // 新宿線
   case 12 :
     printf("岩本町-本八幡間は山手線外なので選択できません。\n");

     printf("[13]新宿駅  [85]新宿三丁目駅 [96]曙橋駅 [32]市ヶ谷駅 [90]九段下駅\n");
     printf("[68]神保町駅 [97]小川町駅\n");
     
     break;

     // 大江戸線
   case 13 :
     printf("汐留-上野御徒町間、新宿西口-光が丘間は山手線外のため選択できません。\n");

     printf("[ 13]新宿駅   [ 12]代々木駅   [ 98]国立競技場駅 [ 38]青山一丁目駅 [ 87]六本木駅\n");
     printf("[ 72]麻布十\番駅 [ 99]赤羽橋駅   [ 95]大門駅    [100]東新宿駅   [101]若松河田駅\n");
     printf("[102]牛込柳町駅 [103]牛込神楽坂駅 [ 33]飯田橋駅   [ 69]春日駅    [ 81]本郷三丁目駅\n");

     break;

   default:
     return 1;

   }

   printf("----------------------------------------------------------------------------\n"); 
   printf("到着駅を選択してください:"); scanf("%d",&t);

   if(s==t){
     printf("出発駅と到着駅が同じです。もう一度やり直してください。\n\n");
     strcpy(a, "終了するには何かキーを押してください...\n");
     printf(a);

     if (getch()) return;
   }



     /* 最短経路探索開始 */
     shortest_path(s,t,path);

     putchar('\n');
     printf("============================================================================\n");
     putchar('\n');


     printf("目的地までの最短経路は以下のようになります。\n");
     printf("-----------------------------------------------\n");
     /* 目的地までの途中表示 */
     for(i=0;path[i]!=t;i++){
       printf("%s-->",&station[path[i]][0]);
     }
     
     /* 目的地 */
     printf("%s\n",&station[t][0]);

     printf("\n\n");


     strcpy(a, "終了するには何かキーを押してください...\n");
     printf(a);

     if (getch()) return;

}