fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. typedef struct //構造体の定義
  6. {
  7.   int s_name;  //駅名
  8.   double lati, longi;  //緯度 経度
  9.   int s_n; //接続している駅の数
  10.   int s_neigh[5];  //接続している駅名
  11.   int visit;  //探索済みであるかどうかを格納する値
  12.   int ps_name;  //探索した親の駅名
  13. }station;
  14.  
  15.  
  16.  
  17. double compute_edge_weight(station st[], int v, int w){//隣接する駅同士の距離を平方根で求める
  18.     return sqrt((st[v].lati - st[w].lati) * (st[v].lati - st[w].lati) + 
  19.     (st[v].longi - st[w].longi) * (st[v].longi - st[w].longi));
  20. }
  21.  
  22. void add(int s[], int u){//最短距離が確定した駅を格納する関数
  23.   s[u] = 1;
  24. }
  25.  
  26. select_min(double d[], int s[]){//暫定距離が最小の要素を選ぶ関数
  27.   int min = 999,i,u;
  28.   for (i=0; i < 6; i++) {
  29.     if (s[i] == 0 && d[i] < min){
  30.       min = d[i];
  31.       u = i;
  32.     }
  33.   }
  34.   return u;
  35. } 
  36.  
  37.  
  38. void search_path(station st[], double d[], int s[], int v){  //再帰的に経路を探索する関数 駅の構造体、探索したかどうかを記憶する配列、スタート地点の駅IDを引数にとる
  39.   int w, u, i,l;
  40.   double j, k;
  41.   st[v].visit = 1; //探索済みなので1を代入
  42.   if(st[v].s_name == 5) return;  //ゴールに到達すれば関数を抜ける
  43.   for(w = 0; w < st[v].s_n; w++){ //隣接する駅の数だけループ
  44.     d[st[v].s_neigh[w]] = d[v] + compute_edge_weight(st, v, st[v].s_neigh[w]);  //原点から現在の駅間での距離プラス現在の駅から隣接する駅までの距離の値を配列に代入
  45.  
  46.   }
  47.   for(w = 0; w < st[v].s_n; w++){//隣接する駅の数だけループ
  48.     if(s[st[v].s_neigh[w]] != 1){//隣接する駅が最短距離だと確定していなければ
  49.       u = select_min(d, s);//隣接する駅から最小の距離のものを探し出し
  50.       add(s, u);//それを最短距離が確定した駅に格納
  51.       //st[u].ps_name = st[v].s_name;  //隣接する駅の親IDにこの駅のIDを入れる
  52.       for(i = 0; i < st[u].s_n; i++){//最短距離の確定した駅から隣接する駅の数だけループ
  53.         if(d[u] != 999 && s[st[u].s_neigh[i]] == 0){//暫定的な最短距離が入力されていて,かつ最短距離が確定していなければ
  54.           k = compute_edge_weight(st, u, st[u].s_neigh[i]);
  55.           if((j = d[u] + k) < d[st[u].s_neigh[i]]){//駅番号uの駅を経由して駅に行ったときの距離が暫定的な最短距離よりも短ければ
  56.             d[st[u].s_neigh[i]] = j;//その距離を新たに代入
  57.             //st[st[u].s_neigh[i]].ps_name = st[u].s_name;  
  58.           }
  59.         }
  60.       }
  61.     }
  62.   }
  63.   for(w = 0; w < st[v].s_n; w++){  //隣接する駅の数だけループ
  64.     if(st[st[v].s_neigh[w]].visit != 1 && st[v].s_neigh[w] != u){  //隣接する駅のIDがすでに探索済みで無ければ
  65.       search_path(st, d, s, st[v].s_neigh[w]);  //未探索の隣接する駅のIDを引数にし再帰的定義
  66.     }
  67.  }
  68. }
  69.  
  70. void display_path(station st[], int v){  //発見した経路を表示する関数 ゴールの駅IDを引数にとる
  71.   if(st[v].s_name  != 0)  //駅IDがスタート地点でなければ
  72.     display_path(st, st[v].ps_name);  //親の駅のIDで再帰的に定義
  73.   printf("駅ID:%d, 駅名:%s\n", st[v].s_name, st[v].s_name);  //スタックの一番上の値から順に表示
  74. }
  75.  
  76. int main(void){
  77.   int i;
  78.   double d[6];//0駅からある駅までの最少距離を入れる配列
  79.   int s[6];//最小距離が確定した駅の番号を入れる配列
  80.   station st[6];
  81.  
  82.   st[0].s_name = 0;
  83.   st[0].lati = 0;
  84.   st[0].longi = 0;
  85.   st[0].s_n = 3;
  86.   st[0].s_neigh[0] = 1;
  87.   st[0].s_neigh[1] = 2;
  88.   st[0].s_neigh[2] = 3;
  89.  
  90.   st[1].s_name = 1;
  91.   st[1].lati = 3;
  92.   st[1].longi = 5;
  93.   st[1].s_n = 2;
  94.   st[1].s_neigh[0] = 0;
  95.   st[1].s_neigh[1] = 5;
  96.  
  97.  
  98.   st[2].s_name = 2;
  99.   st[2].lati = 4;
  100.   st[2].longi = 0;
  101.   st[2].s_n = 4;
  102.   st[2].s_neigh[0] = 0;
  103.   st[2].s_neigh[1] = 1;
  104.   st[2].s_neigh[2] = 3;
  105.   st[2].s_neigh[3] = 4;
  106.  
  107.  
  108.   st[3].s_name = 3;
  109.   st[3].lati = 2;
  110.   st[3].longi = 3;
  111.   st[3].s_n = 3;
  112.   st[3].s_neigh[0] = 0;
  113.   st[3].s_neigh[1] = 2;
  114.   st[3].s_neigh[2] = 4;
  115.  
  116.  
  117.   st[4].s_name = 4;
  118.   st[4].lati = 6;
  119.   st[4].longi = 4;
  120.   st[4].s_n = 3;
  121.   st[4].s_neigh[0] = 2;
  122.   st[4].s_neigh[1] = 3;
  123.   st[4].s_neigh[2] = 5;
  124.  
  125.  
  126.   st[5].s_name = 5;
  127.   st[5].lati = 9;
  128.   st[5].longi = 2;
  129.   st[5].s_n = 2;
  130.   st[5].s_neigh[0] = 1;
  131.   st[5].s_neigh[1] = 4;
  132.  
  133.   for(i = 0; i < 6; i++){//最少距離に無限大を入れて初期化
  134.     d[i] = 999;
  135.   }
  136.   s[0] = 1;//原点の0駅初期化
  137.   d[0] = 0;
  138.   search_path(st, d, s, 0);
  139.   //display_path(st, 5);
  140.   printf("%f", d[5]);
  141.    return 0;
  142. }
Runtime error #stdin #stdout 0.02s 1716KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/G5lEt
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!