6 グラフアルゴリズム：DijkstraのアルゴリズムおよびFloydのアルゴリズムの実装
ソースコードは，次のURLからダウンロードできる．
6.1 基本課題1：Dijkstra法の実装
ヘッダファイル common.h
#ifndef _COMMON_H_
#define _COMMON_H_
#define N 8
#define M INT_MAX
static int const w[N][N] = {
// グラフ1
{0, M, M, 29, M, M, M, 11},
{M, 0, M, 3, M, M, M, 12},
{M, M, 0, M, M, 9, M, M},
{M, 13, M, 0, M, M, M, M},
{M, M, M, M, 0, M, M, 21},
{M, M, 19, 22, M, 0, 9, M},
{M, M, M, M, M, M, 0, 29},
{M, 11, M, 22, 28, 12, M, 0}
// グラフ2
/*
{0, M, 9, 29, M, M, M, 4},
{28, 0, M, M, 14, M, M, M},
{M, 2, 0, M, 27, M, M, M},
{M, M, M, 0, M, M, M, M},
{M, M, M, M, 0, M, 6, 25},
{M, 4, 23, M, M, 0, 19, M},
{M, M, M, 3, 25, M, 0, M},
{M, M, M, M, 21, 26, 17, 0}
*/
};
#endif
ヘッダファイル dijkstra_util.h
#ifndef _DIJKSTRA_UTIL_H_
#define _DIJKSTRA_UTIL_H_
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
void add(int u, bool S[]);
bool remain();
int select_min();
bool member(int u, int x);
void display(char* name, int* ary);
void display_path(int* ary, int origin);
#endif
ソースファイル dijkstra_util.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include "common.h"
extern bool S[N];
extern int Scount; // 頂点集合Sの要素数
extern int d[N];
/**
* 頂点集合 S に頂点 u を追加する．
* @param u 追加する頂点
* @param S 頂点集合
* @return なし
*/
void add(int u, bool S[]) {
// 基本課題1で作成
}
/**
* 頂点集合のうち S に追加されていない頂点があるかどうか確認する．
* @return S に追加されていない頂点が存在すれば true，それ以外は false
*/
bool remain() {
// 基本課題1で作成
}
/**
* p からの最短距離が確定していない頂点のうち，d[] が最小の頂点を
* 返す．
* @param なし
* @return 未確定の d[] が最小の頂点
*/
int select_min() {
// 基本課題1で作成
}
/**
* 頂点 u から頂点 x に接続する辺が存在すれば true, それ以外は
* false を返す.
* @param u 頂点
* @param x 頂点
* @return 辺が存在すれば true, それ以外は false
*/
bool member(int u, int x) {
// 基本課題1で作成
}
/**
* 配列の中身を標準出力に表示．結果出力およびデバッグ用．
* @param name ラベル（変数名など）
* @param ary 配列
* @return なし
*/
void display(char* name, int* ary) {
printf("%s: [", name);
for (int i = 0; i < N; i++) {
if (ary[i] == M)
printf(" M");
else
printf(" %d", ary[i]);
}
printf(" ]\n");
}
/**
* display_path 配列を元に各頂点からの最短経路を表示．
* @param parent int配列
* @param origin 出発点
* @return なし
*/
void display_path(int* parent, int origin) {
// 基本課題2で作成
}
ソースファイル main_dijkstra.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include "dijkstra_util.h"
#include "common.h"
bool S[N];
int Scount = 0; // 頂点集合Sの要素数
int d[N];
/**
* ダイクストラ法で，頂点 p から各頂点への最短路の重みを計算する．
* @param p 開始点
* @return なし
*/
void dijkstra(int p) {
add(p, S);
for (int i = 0; i < N; i++)
d[i] = w[p][i];
while (remain()) {
int u = select_min();
if (u == -1)
break;
else
add(u, S);
for (int x = 0; x < N; x++) {
if (member(u, x)) {
int k = d[u] + w[u][x];
if (d[x] == M)
d[x] = k;
else if (k < d[x])
d[x] = k;
}
}
}
}
/**
* メイン関数．
* @param argc
* @param argv
* @return 終了ステータス 0
*/
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: ./main_dijkstra <node ID>\n");
return 1;
}
int p = atoi(argv[1]);
if (p < 0 || N <= p) {
fprintf(stderr, "Node ID %d is out of range: [0, %d].\n", p, N);
return 1;
}
for (int i = 0; i < N; i++)
S[i] = false;
dijkstra(p); // ダイクストラ法による最短路の計算
display("d", d); // 結果表示
return 0;
}
ファイル Makefile
#CC = gcc
#CFLAGS = -g
all: main_dijkstra main_dijkstra_path main_floyd
main_dijkstra: main_dijkstra.o dijkstra_util.o
main_dijkstra_path: main_dijkstra_path.o dijkstra_util.o
main_floyd: main_floyd.o
clean:
/bin/rm -f main_dijkstra main_dijkstra_path main_floyd *.o *~
コンパイルと実行
$ make main_dijkstra
cc -c -o main_dijkstra.o main_dijkstra.c
cc -c -o dijkstra_util.o dijkstra_util.c
cc main_dijkstra.o dijkstra_util.o -o main_dijkstra
$ ./main_dijkstra 1
d: [ M 0 43 3 40 24 33 12 ]
基本課題1の説明1
上記ソースコード中の以下の関数を実装し，プログラムを完成させなさい． なお，dijkstra関数も必要に応じて修正しても良い． ソースコードにない関数や変数も必要に応じて定義して構わない． ただし，すでにある関数の変更（名前の変更，返り値，引数の変更など）はしないこと．
-
dijkstra_util.cvoid add(int u, bool S[])- 頂点 u を集合 S に追加．
bool remain()- 訪問可能かつ未訪問お頂点があれば true，そうでなければ falseを返す．
int select_min()- 未訪問の頂点のうち最小コストで訪問可能な頂点を返す．
member(int u, int x)- 頂点 u から頂点 x に辺があれば true，それ以外は false を返す．
-
作成したプログラムを，サンプルコード中のグラフ1およびグラフ2に適用し，作成したプログラムが正しく動作していることを確認すること．
- いくつかの開始点
- 選択した開始点から各頂点までの重み
ヒント
到達不能な頂点があるときにも正しい結果が出力されるようにするためには， 以下のようにすると良い．
- select_min関数では，到達可能な点が存在しない場合，失敗（-1）を返す．
- dijkstra関数では，select_min関数が失敗した場合，探索を終了する．
また，無限大（M）を整数の最大値（MAX_INT）で表現している． この値にさらに数値を加算すると値が負になってしまうので，注意すること．
6.2 基本課題2：Dijkstra法における最短路の表示
ソースファイル main_dijkstra_path.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include "dijkstra_util.h"
#include "common.h"
bool S[N];
int Scount = 0; // 頂点集合Sの要素数
int d[N];
int parent[N];
/**
* ダイクストラ法で，頂点 p から各頂点への最短路の重みを計算する．
* @param p 開始点
* @return なし
*/
void dijkstra(int p) {
add(p, S);
for (int i = 0; i < N; i++) {
d[i] = w[p][i];
// (A)parent[i] = p;
}
while (remain()) {
int u = select_min();
if (u == -1)
break;
else
add(u, S);
for (int x = 0; x < N; x++) {
if (member(u, x)) {
int k = d[u] + w[u][x];
if (d[x] == M) {
d[x] = k;
// (B)
} else if (k < d[x])
d[x] = k;
}
}
}
}
/**
* メイン関数．
* @param argc
* @param argv
* @return 終了ステータス 0
*/
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: ./main_dijkstra <node ID>\n");
return 1;
}
int p = atoi(argv[1]);
if (p < 0 || N <= p) {
fprintf(stderr, "Node ID %d is out of range: [0, %d].\n", p, N);
return 1;
}
for (int i = 0; i < N; i++)
S[i] = false;
dijkstra(p); // ダイクストラ法による最短路の計算
display("d", d); // 結果表示
display_path(parent, p);
return 0;
}
コンパイルと実行
$ make main_dijkstra_path
cc -c -o main_dijkstra_path.o main_dijkstra_path.c
cc main_dijkstra_path.o dijkstra_util.o -o main_dijkstra_path
$ ./main_dijkstra_path 1
d: [ M 0 43 3 40 24 33 12 ]
From 1 to 0 (w = M): unreachable
From 1 to 1 (w = 0): 1
From 1 to 2 (w = 43): 1 7 5 2
...
基本課題2の説明
最短路の重みに加えて，出発点から各頂点への最短路も出力するようにプログラムを拡張しなさい．
-
main_dijkstra_path.c中の関数 dijkstra において以下の変更を行う．- 各頂点の最短路における直前の頂点を格納する配列 parent[] を用意する．
- サンプルコード中の (A) において parent[i] = p も行う．
- (B) において，parent[x] = u を実行する．
-
dijkstra_util.cにおいて，最短路の探索が終了後に，配列 parent[] を使って最短路を求める関数 display_path を完成させる．- 必要に応じて，変数や関数を追加しても構わない．
- ただし，定義ずみの関数や変数は変更しないこと．
-
作成したプログラムを，サンプルコード中のグラフ1およびグラフ2に適用し，作成したプログラムが正しく動作していることを確認すること．
- いくつかの開始点
- 選択した開始点から各頂点までの最短経路およびその重み
6.3 発展課題：Floydのアルゴリズムの実装
ソースコード main_floyd.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include "common.h"
int d[N][N];
int p[N][N];
int stack[N];
int stack_p = -1;
/**
* Floydのアルゴリズムで，全ての頂点間の最短経路と重みを計算．
* @return なし
*/
void floyd() {
// 発展課題で作成
}
/**
* 頂点mからnまでの最短路を出力．
* @param m 始点
* @param n 終点
* @return なし
*/
void shortest_path(int m, int n) {
// 発展課題で作成
}
/**
* 任意の頂点間の最短路及び重さを表示．
* @return 終了ステータス 0
*
*/
void display() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 必要な処理を補う
shortest_path(i, j);
}
}
}
/**
* メイン関数．
* @return 終了ステータス 0
*/
int main() {
floyd();
display();
return 0;
}
コンパイルと実行
$ make main_floyd
cc -c -o main_floyd.o main_floyd.c
cc main_floyd.o -o main_floyd
$ ./main_floyd
From 0 to 0 (w = 0): 0
From 0 to 1 (w = 22): 0 7 1
From 0 to 2 (w = 42): 0 7 5 2
From 0 to 3 (w = 25): 0 7 1 3
...
発展課題の説明
-
Floydのアルゴリズムに基づいて，任意の頂点から各頂点への最短路およびその重みを出力するプログラムを作成しなさい．
void floyd()- スライドを元に作成．
void shortest_path(int m, int n)- スライドを元に作成．
- スタックを利用するため，必要な関数や変数を追加する．
-
作成したプログラムを，サンプルコード中のグラフ1およびグラフ2に適用し，作成したプログラムが正しく動作していることを確認すること．
- いくつかの開始点
- 選択した開始点から各頂点までの最短経路およびその重み
6.4 提出ファイルの構成
- ディレクトリ
class6を作成して，その中に上記ファイルを配置すること． class6を ZIP で圧縮したclass6.zipファイルを manaba に提出すること．
```text [class6.zip）の構造] class6/ +- report6.pdf +- Makefile +- common.h +- dijkstra_util.c +- dijkstra_util.h +- main_dijkstra.c +- main_dijkstra_path.c +- main_floyd.c
6.5 提出締切
2025年1月6日（月）13:30