【C言語】最短経路問題を解くアルゴリズム【ダイクストラ法，ワーシャル・フロイド法】

悩んでいる人

C言語で最短経路問題を解くアルゴリズムを教えて！

こういった悩みにお答えします．

本記事の信頼性

リアルタイムシステムの研究歴12年．
東大教員の時に，英語でOS（Linuxカーネル）の授業．
2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Verse（UEFN）, Assembler (x64，aarch64)．
東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
最近は自然言語処理AIとイーサリアムに関する有益な情報発信や，Unreal Editor for Fortnite（UEFN）でゲーム開発に従事．

（AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でChatGPT/Geminiを訓練するプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
（スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
UEFNで10本以上のゲームを開発し，フォートナイト上で公開（Fortnite，Fortnite.GG）．

こういった私から学べます．

C言語を独学で習得することは難しいです．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る

最短経路問題

最短経路問題とは，グラフ理論において重み付きグラフの与えられた2つのノード間を結ぶ経路の中で，重みが最小の経路を求める最適化問題です．

最短経路問題は，主に単一始点最短経路問題（SSSP：Single Source Shortest Path）と全ペア対最短経路問題（APSP : All Pair Shortest Path）の2種類があります．

本記事では，単一始点最短経路問題の代表的なアルゴリズムであるダイクストラ法と，全ペア対最短経路問題の代表的でアルゴリズムであるワーシャル・フロイド法を紹介します．

最短経路問題：ダイクストラ法

ダイクストラ法は，1959年にエドガー・ダイクストラにより提案されたグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムです．

ダイクストラ法は，最短経路問題を解く代表的なアルゴリズムで，Open Shortest Path First（OSPF）等のインターネットルーティングプロトコルや，カーナビの経路探索や鉄道の経路案内に利用されています．

ダイクストラ法の解説は，こちらの動画がわかりやすいです．

ダイクストラ法のコードは以下になります．

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdbool.h>
#include <stdio.h>
#include <limits.h>

#define NODES 5

int min_distance(int dist[], bool is_shotest_path_set[])
{
  int min = INT_MAX;
  int min_index;
  int i;

  for (i = 0; i < NODES; i++) {
    if (!is_shotest_path_set[i] && dist[i] < min) {
      min = dist[i];
      min_index = i;
    }
  }

  return min_index;
}

void print_path(int parent[], int j)
{
  if (parent[j] == INT_MAX) {
    return;
  }

  print_path(parent, parent[j]);
  printf("->%d", j);
}

void print_solution(int dist[], int parent[])
{
  int i;
  printf("Node\tDistance\tPath of Start to Goal");

  for (i = 1; i < NODES; i++) {
    printf("\n%d->%d\t%d\t\t%d", 0, i, dist[i], 0);
    print_path(parent, i);
  }

  printf("\n");
}

void do_dijkstra(int graph[NODES][NODES])
{
  int dist[NODES];
  bool is_shotest_path_set[NODES] = {false};
  int parent[NODES] = {INT_MAX};
  int i, j, k;

  for (i = 0; i < NODES; i++) {
    dist[i] = INT_MAX;
  }

  /* assume that 0 is start node. */
  dist[0] = 0;

  for (i = 0; i < NODES - 1; i++) {
    j = min_distance(dist, is_shotest_path_set);
    is_shotest_path_set[j] = true;

    for (k = 0; k < NODES; k++) {
      if (!is_shotest_path_set[k] && dist[j] < dist[k] - graph[j][k]) {
        parent[k] = j;
        dist[k] = dist[j] + graph[j][k];
      }
    }
  }

  print_solution(dist, parent);
}

int main(void)
{
  int graph[NODES][NODES] = {
    {0, 1, INT_MAX, INT_MAX, 4},
    {1, 0, 3, 1, 3},
    {INT_MAX, 3, 0, 1, INT_MAX},
    {INT_MAX, 1, 1, 0, 1},
    {4, 3, INT_MAX, 1, 0},
  };

  do_dijkstra(graph);
  return 0;
}

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdbool.h>

#include <stdio.h>

#include <limits.h>

#define NODES 5

int min_distance(int dist[], bool is_shotest_path_set[])

{

int min = INT_MAX;

int min_index;

int i;

for (i = 0; i < NODES; i++) {

if (!is_shotest_path_set[i] && dist[i] < min) {

min = dist[i];

min_index = i;

}

return min_index;

}

void print_path(int parent[], int j)

{

if (parent[j] == INT_MAX) {

return;

}

print_path(parent, parent[j]);

printf("->%d", j);

}

void print_solution(int dist[], int parent[])

{

int i;

printf("Node\tDistance\tPath of Start to Goal");

for (i = 1; i < NODES; i++) {

printf("\n%d->%d\t%d\t\t%d", 0, i, dist[i], 0);

print_path(parent, i);

}

printf("\n");

}

void do_dijkstra(int graph[NODES][NODES])

{

int dist[NODES];

bool is_shotest_path_set[NODES] = {false};

int parent[NODES] = {INT_MAX};

int i, j, k;

for (i = 0; i < NODES; i++) {

dist[i] = INT_MAX;

}

/* assume that 0 is start node. */

dist[0] = 0;

for (i = 0; i < NODES - 1; i++) {

j = min_distance(dist, is_shotest_path_set);

is_shotest_path_set[j] = true;

for (k = 0; k < NODES; k++) {

if (!is_shotest_path_set[k] && dist[j] < dist[k] - graph[j][k]) {

parent[k] = j;

dist[k] = dist[j] + graph[j][k];

}

print_solution(dist, parent);

}

int main(void)

{

int graph[NODES][NODES] = {

{0, 1, INT_MAX, INT_MAX, 4},

{1, 0, 3, 1, 3},

{INT_MAX, 3, 0, 1, INT_MAX},

{INT_MAX, 1, 1, 0, 1},

{4, 3, INT_MAX, 1, 0},

};

do_dijkstra(graph);

return 0;

}

実行結果は以下になります．

$ gcc dijkstra.c 
$ a.out 
Node    Distance        Path of Start to Goal
0->1    1               0->1
0->2    3               0->1->3->2
0->3    2               0->1->3
0->4    3               0->1->3->4

$ gcc dijkstra.c

$ a.out

Node Distance Path of Start to Goal

0->1 1 0->1

0->2 3 0->1->3->2

0->3 2 0->1->3

0->4 3 0->1->3->4

全ペア最短経路問題：ワーシャル・フロイド法

ワーシャル・フロイド法は，スティーブン・ワーシャルとロバート・フロイドが独立に提案した重み付き有向グラフの全ペア最短経路問題を多項式時間で解くアルゴリズムです．

ダイクストラ法は単一始点最短経路問題を解く代表的なアルゴリズムなのに対して，ワーシャル・フロイド法は全ペアの最短経路問題を解く代表的なアルゴリズムになります．

ワーシャル・フロイド法の解説は，こちらの動画がわかりやすいです．

ワーシャル・フロイド法のコードは以下になります．

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <limits.h>

#define NODES 5

void print_solution(int dist[][NODES])
{
  int i, j;

  printf("[The shortest distances between every pair of nodes]\n");
  printf("Node|");

  for (i = 0; i < NODES; i++) {
    printf("%4d", i);
  }

  printf("\n");

  for (i = 0; i < NODES; i++) {
    printf("-----");
  }

  printf("\n");

  for (i = 0; i < NODES; i++) {
    printf("%4d|", i);

    for (j = 0; j < NODES; j++) {
      if (dist[i][j] == INT_MAX) {
        printf("%4s", " INF");
      } else {
        printf("%4d", dist[i][j]);
      }
    }

    printf("\n");
  }
}

void do_warshall_floyd(int graph[][NODES])
{
  int dist[NODES][NODES];
  int i, j, k;

  for (i = 0; i < NODES; i++) {
    for (j = 0; j < NODES; j++) {
      dist[i][j] = graph[i][j];
    }
  }

  for (k = 0; k < NODES; k++) {
    for (i = 0; i < NODES; i++) {
      for (j = 0; j < NODES; j++) {
        if (dist[i][k] < dist[i][j] - dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  print_solution(dist);
}

int main(void)
{
  int graph[NODES][NODES] = {
    {0, 1, INT_MAX, INT_MAX, 4},
    {1, 0, 3, 1, 3},
    {INT_MAX, 3, 0, 1, INT_MAX},
    {INT_MAX, 1, 1, 0, 1},
    {4, 3, INT_MAX, 1, 0},
  };

  do_warshall_floyd(graph);
  return 0;
}

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <limits.h>

#define NODES 5

void print_solution(int dist[][NODES])

{

int i, j;

printf("[The shortest distances between every pair of nodes]\n");

printf("Node|");

for (i = 0; i < NODES; i++) {

printf("%4d", i);

}

printf("\n");

for (i = 0; i < NODES; i++) {

printf("-----");

}

printf("\n");

for (i = 0; i < NODES; i++) {

printf("%4d|", i);

for (j = 0; j < NODES; j++) {

if (dist[i][j] == INT_MAX) {

printf("%4s", " INF");

} else {

printf("%4d", dist[i][j]);

}

printf("\n");

}

void do_warshall_floyd(int graph[][NODES])

{

int dist[NODES][NODES];

int i, j, k;

for (i = 0; i < NODES; i++) {

for (j = 0; j < NODES; j++) {

dist[i][j] = graph[i][j];

}

for (k = 0; k < NODES; k++) {

for (i = 0; i < NODES; i++) {

for (j = 0; j < NODES; j++) {

if (dist[i][k] < dist[i][j] - dist[k][j]) {

dist[i][j] = dist[i][k] + dist[k][j];

}

print_solution(dist);

}

int main(void)

{

int graph[NODES][NODES] = {

{0, 1, INT_MAX, INT_MAX, 4},

{1, 0, 3, 1, 3},

{INT_MAX, 3, 0, 1, INT_MAX},

{INT_MAX, 1, 1, 0, 1},

{4, 3, INT_MAX, 1, 0},

};

do_warshall_floyd(graph);

return 0;

}

実行結果は以下になります．

$ gcc warshall_floyd.c
$ a.out 
[The shortest distances between every pair of nodes]
Node|   0   1   2   3   4
-------------------------
   0|   0   1   3   2   3
   1|   1   0   2   1   2
   2|   3   2   0   1   2
   3|   2   1   1   0   1
   4|   3   2   2   1   0

$ gcc warshall_floyd.c

$ a.out

[The shortest distances between every pair of nodes]

Node| 0 1 2 3 4

-------------------------

0| 0 1 3 2 3

1| 1 0 2 1 2

2| 3 2 0 1 2

3| 2 1 1 0 1

4| 3 2 2 1 0

まとめ

C言語で最短経路問題を解くアルゴリズムを紹介しました．

具体的には，ダイクストラ法，ワーシャル・フロイド法を解説しました．

どちらも代表的なアルゴリズムなのできちんと理解しておきましょう！

C言語を独学で習得することは難しいです．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る