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;
}