グラフアルゴリズム

DijkstraのアルゴリズムおよびFloydのアルゴリズムの実装

以下のソースコードは，次のURLからダウンロードできる．

ソースコード： https://www.coins.tsukuba.ac.jp/~amagasa/lecture/dsa-files/dsa-code-graph.zip

ヘッダファイル common.h

#ifndef _COMMON_H_
#define _COMMON_H_

#define N 6
#define M INT_MAX

#endif

ソースファイル dijkstra.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>  // stdbool.hヘッダーファイルをインクルード
#include <limits.h>
#include "common.h"

extern int w[N][N];
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[]) {
  // 関数を完成させる．

}

/**
 * 頂点集合のうち S に追加されていない頂点があるかどうか確認する．
 * @return S に追加されていない頂点が存在すれば true，それ以外は false
 */
static bool remain() {
  // 関数を完成させる．

}

/**
 * p からの最短距離が確定していない頂点のうち，d[] が最小の頂点を
 * 返す．
 * @param なし
 * @return 未確定の d[] が最小の頂点
 */
int select_min() {
  // 関数を完成させる．

}

/**
 * 頂点 u から頂点 x に接続する辺が存在すれば true, それ以外は
 * false を返す.
 * @param u 頂点
 * @param x 頂点
 * @return 辺が存在すれば true, それ以外は false
 */
bool member(int u, int x) {
  // 関数を完成させる．

}

/**
 * ダイクストラ法で，頂点 p から各頂点への最短路の重みを計算する．
 * @param p 開始点
 * @return なし
 */
void dijkstra(int p) {
  add(p, S);

  for (int i = 0; i < N; i++) {
    d[i] = w[p][i];
    // (A)
  }

  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];
    // (B)
    if (d[x] == M)
      d[x] = k;
    else if (k < d[x])
      d[x] = k;
      }
    }
  }
}

/**
 * 配列の中身を標準出力に表示．結果出力およびデバッグ用．
 * @param name ラベル（変数名など）
 * @param ary 配列
 * @return なし
 */
void display(char* name, int* ary, int length) {
  printf("%s: [", name);
  for (int i = 0; i < length; i++) {
    if (ary[i] == M)
      printf(" M");
    else
      printf(" %d", ary[i]);
  }
  printf(" ]\n");
}

ソースファイル main.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include "common.h"

int w[N][N] = {
  { 0, M,  M, 8, 15, M},
  {10, 0, 24, M,  8, M},
  { M, M,  0, M,  M, 6},
  { M, M,  M, 0,  5, M},
  { M, M, 12, M,  0, 7},
  { M, M,  3, M,  M, 0}};

bool S[N];
int Scount = 0;                      // 頂点集合Sの要素数
int d[N];

void add(int, bool[]);
bool remain();
int dijkstra(int);
void display(char *, int *, int);

int main(int argc, char *argv[]) {
  if (argc != 2) {
    fprintf(stderr, "Usage: ./main <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("Result", d, N);  // 結果表示

  return 0;
}

コンパイルと実行

以下の Makefile を作成する．

ファイル Makefile

main: dijkstra.o main.o

コマンドラインでmakeコマンドを実行すると，Cコンパイラによって実行ファイルが生成される．

$ make
cc    -c -o main.o main.c
cc    -c -o dijkstra.o dijkstra.c
cc   main.o dijkstra.o   -o main

main コマンドの引数に出発頂点を与えて実行すると，その頂点から各頂点まっでの最短経路の重みが出力される．

$ ./main 1
Result: [ 10 0 18 18 8 15 ]

基本課題1

上記ソースコードにおいてブランクになっている関数を実装し，プログラムを完成させなさい．なお，dijkstra関数も必要に応じて修正すること．

ヒント

到達不能な頂点があるときにも正しい結果が出力されるようにするためには，以下のようにすると良い．

select_min関数では，到達可能な点が存在しない場合，失敗（-1）を返す．
dijkstra関数では，select_min関数が失敗した場合，探索を終了する．

また，無限大（M）を整数の最大値（MAX_INT）で表現している．この値にさらに数値を加算すると値が負になってしまうので，注意すること．

基本課題2

作成したプログラムを，サンプルコード中のグラフおよびサンプル以外のグラフ（ただし，グラフのサイズは同じかより大きいものとする）にに適用しなさい．レポートでは，

確認に使用したグラフ
開始点
開始点から各頂点まで最短経路の重みの和

を示し，それがプログラムで正しく計算されていることを，二つ以上の開始点で確認すること．

基本課題3

最短路の重みに加えて，出発点から各頂点への最短路も出力するようにプログラムを拡張しなさい．

ヒント

各頂点の最短路における直前の頂点を格納する配列 parent[] を用意する．
サンプルコード中の (A) において parent[i] = p も行う．
(B) において，parent[x] = u を実行する．
最短路の探索が終了後に，配列 parent[] を使って最短路を求める関数を作成する．

発展課題

Floydのアルゴリズムに基づいて，任意の頂点から各頂点への最短路およびその重みを出力するプログラムを作成しなさい．
作成したプログラムを，サンプルコード中のグラフおよび必須課題2で使用したグラフにに適用しなさい．レポートでは，
- 確認に使用したグラフ
- いくつかの開始点
- 選択した開始点から各頂点までの最短経路およびその重み
を示し，それがプログラムで正しく計算されていることを確認しなさい．

補足：ランダムなグラフの生成

以下は，ランダムにグラフを生成して，それに基づいた隣接行列を生成するプログラムである．サンプルの隣接行列以外のよりサイズの大きなグラフを生成する際に使うと便利かもしれない．（使わなくても構わない．）

ソースコード： https://www.coins.tsukuba.ac.jp/~amagasa/lecture/dsa-files/RandomDigraph.java
使い方：java RandomDigraph <頂点数> <辺の生成確率 [0, 1]> <辺の重みの最大値>

例：

% javac RandomDigraph.java % java RandomDigraph 10 0.5 30 int w[N][N] = { {0,13,M,M,M,27,M,8,10,M}, {M,0,26,5,15,M,M,3,5,15}, {M,M,0,28,M,11,M,19,M,M}, {M,21,M,0,M,M,M,14,15,11}, {16,M,M,M,0,M,M,25,M,25}, {M,M,M,4,29,0,7,M,M,M}, {18,M,12,2,M,12,0,M,M,8}, {10,6,7,12,M,M,25,0,M,M}, {M,12,M,M,6,M,3,M,0,M}, {13,M,M,13,M,21,4,18,5,0} };

提出締切

2023年1月10日（火）13:30