fork download
copy 
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3.  
  4. #define N (7) /* 地点の数 */
  5.  
  6. /* 地点間距離 */
  7. /* ※1 地点aと地点bが同一の地点の場合は0が格納されている */
  8. /* ※2 地点aと地点bが隣接地点でない場合は-1が格納されている */
  9. /*static*/ int DISTANCE_MAP[N][N] = {
  10.     /*a ->b 0   1   2   3   4   5   6 */
  11.     /*0*/ {+0, +2, +8, +4, -1, -1, -1},
  12.     /*1*/ {+2, +0, -1, -1, +3, -1, -1},
  13.     /*2*/ {+8, -1, +0, -1, +2, +3, -1},
  14.     /*3*/ {+4, -1, -1, +0, -1, +8, -1},
  15.     /*4*/ {-1, +3, +2, -1, +0, -1, +9},
  16.     /*5*/ {-1, -1, +3, +8, -1, +0, +3},
  17.     /*6*/ {-1, -1, -1, -1, +9, +3, +0},
  18. };
  19.  
  20. typedef const char *String;
  21. typedef int Point;
  22. typedef int Distance;
  23. #define Distance_MAX (99999)
  24.  
  25. typedef struct route
  26. {
  27.   Point start, destination;
  28.   Distance distance;
  29.   Point point[N];
  30. } Route;
  31.  
  32. void find_shortest(Route *route)
  33. {
  34.   Point point;
  35.   Distance distance, shortest_distance[N];
  36.   bool fixed[N];
  37.  
  38.   /* 初期化 */
  39.   for (point = 0; point < N; point++)
  40.   {
  41.     shortest_distance[point] = Distance_MAX;
  42.     fixed[point] = false;
  43.   }
  44.   shortest_distance[route->start] = 0;
  45.  
  46.   while (true)
  47.   {
  48.     /* 未確定地点を1つ探す */
  49.     for (point = 0; point < N && fixed[point]; point++)
  50.     {
  51.     }
  52.     if (point == N)
  53.       return;
  54.  
  55.     /* 最短距離がより短い地点を探す */
  56.     for (int i = point + 1; i < N; i++)
  57.     {
  58.       if (!fixed[i] && shortest_distance[i] < shortest_distance[point])
  59.       {
  60.         point = i;
  61.       }
  62.     }
  63.     fixed[point] = true;
  64.  
  65.     /* 距離再計算 */
  66.     for (int i = 0; i < N; i++)
  67.     {
  68.       if (fixed[i])
  69.       {
  70.         continue;
  71.       }
  72.       distance = DISTANCE_MAP[point][i];
  73.       if (distance <= 0)
  74.       {
  75.         continue;
  76.       }
  77.       distance += shortest_distance[point];
  78.       if (distance < shortest_distance[i])
  79.       {
  80.         shortest_distance[i] = distance;
  81.         route->point[i] = point;
  82.       }
  83.     }
  84.     route->distance = shortest_distance[route->destination];
  85.   }
  86. }
  87.  
  88. void print_route(Route *route, Point destination)
  89. {
  90.   /* 目的地から出発地までの経路を逆順にたどって出発地から表示する */
  91.   if (route->start == destination)
  92.   {
  93.     printf("%d", route->start);
  94.   }
  95.   else
  96.   {
  97.     print_route(route, route->point[destination]);
  98.     printf(" -> %d", destination);
  99.   }
  100. }
  101.  
  102. void print_shortest(Route *route)
  103. {
  104.   printf("出発地から目的地までの最短経路\n");
  105.   print_route(route, route->destination);
  106.   printf("\n出発地から目的地までの最短距離 = %d\n", route->distance);
  107. }
  108.  
  109. void init_DISTANCE_MAP()
  110. {
  111.   int i, j;
  112.   for (i = 0; i < N; i++)
  113.   {
  114.     for (j = 0; j < N; j++)
  115.     {
  116.       if (i == j)
  117.       {
  118.         DISTANCE_MAP[i][j] = 99999;
  119.       }
  120.     }
  121.   }
  122. }
  123.  
  124. Point input_point(String prompt)
  125. {
  126.   Point point;
  127.   do
  128.   {
  129.     printf("%s", prompt);
  130.     scanf("%d", &point);
  131.   } while (point > N - 1);
  132.   return point;
  133. }
  134.  
  135. int main()
  136. {
  137.   Route route;
  138.   init_DISTANCE_MAP();
  139.  
  140.   route.start = input_point("出発地の地点番号を入力してください ==> ");
  141.   route.destination = input_point("目的地の地点番号を入力してください ==> ");
  142.   find_shortest(&route);
  143.   print_shortest(&route);
  144.  
  145.   return 0;
  146. }
Success #stdin #stdout 0s 4468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
出発地の地点番号を入力してください ==> 目的地の地点番号を入力してください ==> 出発地から目的地までの最短経路
0
出発地から目的地までの最短距離 = 0
https://ideone.com/snxvav
language:
C (gcc 8.3)
created:
4 years ago
visibility:
secret

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!