質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.31%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

1回答

338閲覧

第K最短路を求めるプログラムを作成したい

evangelist

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2025/04/23 11:13

実現したいこと

与えられた始点と終点に対して k(1≦k≦5)番目まで短い経路の距離を求める.
※ある地点を2度以上通るような無駄な回り道を含む経路はk番目の最短路とはみなさない.

発生している問題・分からないこと

k番目の最短路の計算方法が分からない

該当のソースコード

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #define MAXN 1100 #define MAXM 500 #define MAXQ 100 #define INF 1e18 #define EPS 1e-8 #define MAXK 5 typedef struct { double x, y; } Point; typedef struct { int a, b; } Segment; typedef struct Edge { int to; double cost; struct Edge* next; } Edge; Point points[MAXN]; Segment segs[MAXM]; Edge* graph[MAXN]; int node_count = 0; int equal(Point p1, Point p2) { return fabs(p1.x - p2.x) < EPS && fabs(p1.y - p2.y) < EPS; } double distance(Point p1, Point p2) { double dx = p1.x - p2.x, dy = p1.y - p2.y; return sqrt(dx * dx + dy * dy); } int intersect(Point p1, Point q1, Point p2, Point q2, double* ix, double* iy) { double a = q1.x - p1.x; double b = -(q2.x - p2.x); double c = q1.y - p1.y; double d = -(q2.y - p2.y); double e = p2.x - p1.x; double f = p2.y - p1.y; double det = a * d - b * c; if (fabs(det) < EPS) return 0; double s = (d * e - b * f) / det; double t = (-c * e + a * f) / det; if (s < EPS || s > 1 - EPS || t < EPS || t > 1 - EPS) return 0; *ix = p1.x + s * (q1.x - p1.x); *iy = p1.y + s * (q1.y - p1.y); if (equal((Point){*ix, *iy}, p1) || equal((Point){*ix, *iy}, q1) || equal((Point){*ix, *iy}, p2) || equal((Point){*ix, *iy}, q2)) return 0; return 1; } void add_edge(int u, int v, double cost) { Edge* e = malloc(sizeof(Edge)); e->to = v; e->cost = cost; e->next = graph[u]; graph[u] = e; } int cmp_point(const void* a, const void* b) { Point* p = (Point*)a; Point* q = (Point*)b; if (fabs(p->x - q->x) > EPS) return p->x < q->x ? -1 : 1; if (fabs(p->y - q->y) > EPS) return p->y < q->y ? -1 : 1; return 0; } int get_node_index(Point p) { for (int i = 0; i < node_count; i++) { if (equal(points[i], p)) return i; } points[node_count++] = p; return node_count - 1; } void build_graph(int M) { for (int i = 0; i < M; i++) { Point p1 = points[segs[i].a]; Point p2 = points[segs[i].b]; Point seg_pts[MAXN]; int count = 0; seg_pts[count++] = p1; seg_pts[count++] = p2; for (int j = 0; j < M; j++) { if (i == j) continue; double ix, iy; if (intersect(p1, p2, points[segs[j].a], points[segs[j].b], &ix, &iy)) { seg_pts[count++] = (Point){ix, iy}; } } qsort(seg_pts, count, sizeof(Point), cmp_point); for (int k = 0; k < count - 1; k++) { int u = get_node_index(seg_pts[k]); int v = get_node_index(seg_pts[k + 1]); double d = distance(seg_pts[k], seg_pts[k + 1]); add_edge(u, v, d); add_edge(v, u, d); } } } int parse_node(char* s, int N) { if (s[0] == 'C') { int id = atoi(s + 1); if (id < 1 || id > node_count - N) return -1; return N + id - 1; } else { int id = atoi(s); if (id < 1 || id > N) return -1; return id - 1; } } void reconstruct_path(int start, int goal, int prev[], int N) { int path[MAXN], len = 0; for (int v = goal; v != -1; v = prev[v]) { path[len++] = v; } for (int i = len - 1; i >= 0; i--) { if (path[i] < N) printf("%d", path[i] + 1); else printf("C%d", path[i] - N + 1); if (i > 0) printf(" "); } printf("\n"); } void dijkstra(int start, double dist[], int prev[]) { int used[MAXN] = {0}; for (int i = 0; i < MAXN; i++) { dist[i] = INF; prev[i] = -1; } dist[start] = 0; for (int i = 0; i < node_count; i++) { int v = -1; for (int j = 0; j < node_count; j++) { if (!used[j] && (v == -1 || dist[j] < dist[v])) v = j; } if (v == -1 || dist[v] == INF) break; used[v] = 1; for (Edge* e = graph[v]; e; e = e->next) { if (dist[e->to] > dist[v] + e->cost) { dist[e->to] = dist[v] + e->cost; prev[e->to] = v; } else if (fabs(dist[e->to] - (dist[v] + e->cost)) < EPS) { if (v < prev[e->to]) prev[e->to] = v; } } } } void yen_k_shortest_paths(int start, int goal, int k, double dist[], int prev[]) { double dist_all[MAXK][MAXN]; int prev_all[MAXK][MAXN]; dijkstra(start, dist, prev); memcpy(dist_all[0], dist, sizeof(double) * MAXN); memcpy(prev_all[0], prev, sizeof(int) * MAXN); for (int i = 1; i < k; i++) { double d[MAXN]; int p[MAXN]; memcpy(d, dist_all[i - 1], sizeof(double) * MAXN); memcpy(p, prev_all[i - 1], sizeof(int) * MAXN); } } int main() { int N, M, P, Q; scanf("%d %d %d %d", &N, &M, &P, &Q); for (int i = 0; i < N; i++) { scanf("%lf %lf", &points[i].x, &points[i].y); } node_count = N; for (int i = 0; i < M; i++) { scanf("%d %d", &segs[i].a, &segs[i].b); segs[i].a--; segs[i].b--; } build_graph(M); for (int q = 0; q < Q; q++) { char s1[10], s2[10]; int k; scanf("%s %s %d", s1, s2, &k); int start = parse_node(s1, N); int goal = parse_node(s2, N); if (start == -1 || goal == -1) { printf("NA\n"); continue; } double dist[MAXN]; int prev[MAXN]; yen_k_shortest_paths(start, goal, k, dist, prev); } return 0; }

試したこと・調べたこと

  • teratailやGoogle等で検索した
  • ソースコードを自分なりに変更した
  • 知人に聞いた
  • その他
上記の詳細・結果

セグメンテーションフォールトになってしまった

補足

制約
2≦N≦200, 1≦M<N, 0≦x,y≦104, P=0, 0≦Q≦100.

出力
各始点と終点のペアに対して、k番目まで短い経路の距離を出力する. 存在しない地点に対する問い合わせが来た場合や、到達できない場合はNAと出力する. 最短経路が存在する場合、2番目、3番目、…、k番目に短い経路が存在しなければ、存在しない分は出力しない.

入出力例
入力例
6 5 0 2
0 0
2 5
4 7
5 5
7 1
9 5
1 4
1 6
2 5
3 5
4 6
1 4 5
C1 C3 10

出力例
7.07107
8.65895
8.99493
9.81418
12.7711
2.68432
3.83003
6.79648
9.46671
11.9
16.0121

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

jimbe

2025/04/23 15:57

今提示されているコードはどのような状態なのでしょうか。
evangelist

2025/04/24 02:10

現在作成しているコードは、平面上の点と線分からグラフを作り、交差点もノードとして扱って最短経路(第K最短まで)を求めるプログラムになっています。主な処理としては、点・線分の読み取り、交差点検出&ノード追加、線分上の点をつないでグラフ構築、ダイクストラ法で最短経路探索、Yen’s AlgorithmでK番目までの経路探索を行うようにしていますが、このコードをコンパイルしたところSegmentation fault (core dumped)と表示されました。
int32_t

2025/04/24 02:43

> Segmentation fault (core dumped)と表示されました。 まずはデバッグビルドしてデバッガ上で実行してどこで落ちるのか調べましょう。 あと、何かの課題のように見えますが、ネット上に課題内容を転載したり回答を手伝ってもらったりはOKなものでしょうか。
guest

回答1

0

Segmentation faultの件のみ回答します。

以下の3環境で確認しました。

OSコンパイラー備考
Windows 11Visual Studio 2022先頭に#define _CRT_SECURE_NO_WARNINGS追加
FreeBSD 14.2GCC 15.0.1-lmでコンパイル
FreeBSD 14.2Clang 21.0.0

yen_k_shortest_paths関数で、配列dist_allprev_allが範囲外を参照しています。

for (int i = 1; i < k; i++) { double d[MAXN]; int p[MAXN]; memcpy(d, dist_all[i - 1], sizeof(double) * MAXN); memcpy(p, prev_all[i - 1], sizeof(int) * MAXN); }

両配列とも、サイズは[5][1100]です。
k=5のとき(最後から2番目の入力)では[0]~[3]を参照するので問題無いです。
k=10のとき(最後の入力)では[0]~[8]を参照するので、[5]以降は範囲外です。

実際は範囲外になるとすぐ落ちるわけではなく、メモリーが続く限り不定値をd,pにコピーします。
3環境で試したところ、Visual Studioは落ちませんでしたが、GCC/Clangはdist_all[6]で落ちました。(複数回実行したが同じ)
いずれにしても、[5]以降はコピーしても意味が無いです。

投稿2025/04/26 09:00

hiroki-o

総合スコア1361

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.31%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問