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

実現したいこと

与えられた始点と終点に対して k(1≦k≦5)番目まで短い経路の距離を求める.
※ある地点を２度以上通るような無駄な回り道を含む経路は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と出力する. 最短経路が存在する場合、２番目、３番目、…、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

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なものでしょうか。

行動規範の内容に同意します

回答2件

既に回答されているように #define MAXK 5 と記述しているにもかかわらず入力例の最後の行「C1 C3 10」で k = 10 を指定していることが原因なので，#define MAXK 10 に修正すれば「Segmentation fault」は解消できました。ただし，関数 yen_k_shortest_paths() の記述が途中のようで結果は出力されませんでした。

御参考として，関数 dijkstra() の動作を確認するために最短経路の距離を出力する記述を追加してみたところ下記の結果が得られました。一応，予定している結果が得られているようです。

C
1void yen_k_shortest_paths(int start, int goal, int k,
2                          double dist[], int prev[]) {
3
4    （省略）
5
6    dijkstra(start, dist, prev);
7    printf("P%d ~ P%d: %f\n", start + 1, goal + 1, dist[goal]);  // 追加
8
9    （省略）
10
11}

sh
1P1 ~ P4: 7.071068
2P7 ~ P9: 2.684323

投稿2025/05/07 13:34

little_street

総合スコア437

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

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

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

yen_k_shortest_paths関数で、配列dist_allとprev_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