Page Hopping … グラフ, 全点対間最短路 - Imoのアルゴリズムライブラリ

Page Hopping

問題

Given a graph in which all nodes can be reached from any starting point, your job is to find the average shortest path length between arbitrary pairs of nodes.
引用: UVa 821

概要

グラフが与えられた時、辿り着きうる任意の二点を選んだ時の平均の最短距離を求める

計算量

O(N3)

ソースコード

// Page Hopping
#include <stdio.h>
#include <string.h>

int main(void) {
  int a, b, p = 0, m[100][100];
  while (scanf("%d%d", &a, &b) && a && b) {
    memset(m, 1, sizeof(m)); p++;
    do { m[a - 1][b - 1] = 1; }
     while (scanf("%d%d", &a, &b) && a && b);
    // cf. Floyd Warshall
    for (int k = 0; k < 100; k++)
     for (int i = 0; i < 100; i++)
      for (int j = 0; j < 100; j++)
       if (m[i][k] + m[k][j] < m[i][j])
        m[i][j] = m[i][k] + m[k][j];
    for (int i = 0; i < 100; i++)
     for (int j = 0; j < 100; j++)
      if (i != j && m[i][j] < 100) { a += m[i][j]; b++; }
    printf("Case %d: average length between "
     "pages = %5.3lf clicks\n", p, (double)a / (double)b);
  }
  return 0;
}

確認

• UVa 821

参考

全点対間最短距離

• Page Hopping … グラフ, 全点対間最短路

• Page Hopping … グラフ, 全点対間最短路