みけCATのにっき（仮）
つれづれなるまゝに、日くらし、PCにむかひて、心に移りゆくよしなし事を、そこはかとなく書きつくれば、あやしうこそものぐるほしけれ。
（本当か！？）
出典

O(N^3)の全点対最短路アルゴリズム

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:
みけCAT に連絡する

O(N^3)の全点対最短路アルゴリズム

投稿記事 by みけCAT » 12年前

通常、グラフの全点対最短路を求めるにはワーシャル-フロイド法を使用します。[要出典]
このワーシャル-フロイド法は、グラフの頂点数をNとすると、時間計算量O(N3)で動作します。

ここで、考えました。
ダイクストラ法のある実装はO(N2)であり、ある頂点を始点とするすべての頂点への最短路が求まる。
これを全ての頂点を始点として全部でN回計算すればO(N2×N)、すなわちO(N3)になるのでは？

では、なぜそのようなことはしないのでしょうか。
それは、ダイクストラ法はワーシャル-フロイド法に比べて実装が複雑で、定数倍も重そうだからです。[要出典]
(それでもO(N2)のダイクストラ法は簡単ですが)

だとすれば、実際どの程度定数倍が重いのでしょうか？
試してみましょう。

検証環境
Windows Vista Home Premium SP2 32ビット
gcc 4.7.2
最適化 -O2
実行時間測定 runtime
測定回数　各1回

ワーシャル-フロイド法のコード

CODE: 

#include 

#define N_MAX 5000

int N;
int input[N_MAX][N_MAX];

int main(void) {
	int i,j,k;
	scanf("%d",&N);
	if(N>N_MAX)return 1;
	for(i=0;i=0 && input[k][j]>=0 &&
					(input[i][j]input[i][k]+input[k][j]))
						input[i][j]=input[i][k]+input[k][j];
			}
		}
	}

	for(i=0;i

#define N_MAX 5000

int N;
int input[N_MAX][N_MAX];
int answer[N_MAX][N_MAX];
char confirmed[N_MAX];

int main(void) {
	int i,j;
	int start;
	scanf("%d",&N);
	if(N>N_MAX)return 1;
	for(i=0;i=0 && answer[start][i]=0 &&
						(answer[start][i]
#include 
#include 

static unsigned int x=123456789;
static unsigned int y=362436069;
static unsigned int z=521288629;
static unsigned int w=88675123;

void seed(unsigned int a,unsigned int b,unsigned int c,unsigned int d) {
	if((a|b|c|d)==0)return;
	x=a;y=b;z=c;w=d;
}

unsigned int randint(void) {
	unsigned int t;
	t=(x^(x>19))^(t^(t>>8));
	return w;
}

int main(int argc,char* argv[]) {
	int N;
	int i,j;
	if(argc!=2) {
		fprintf(stderr,"Usage: casegen \n");
		return 1;
	}
	sscanf(argv[1],"%d",&N);
	srand((unsigned int)time(NULL));
	seed(rand(),rand(),rand(),rand());
	printf("%d\n",N);
	for(i=0;i<N;i++) {
		for(j=0;j<N;j++) {
			printf("%d%c",
				i==j?0:(randint()%2==0?(randint()%10001):-1),
				j+1==N?'\n':' ');
		}
	}
	return 0;
}
[/spoil]
測定結果
[table=border:1px solid #ffffff; border-collapse: collapse;][tr=][td=border:1px solid #ffffff; padding: 0.2em;]N[/td][td=border:1px solid #ffffff; padding: 0.2em;]ワーシャル-フロイド法[ms][/td][td=border:1px solid #ffffff; padding: 0.2em;]ダイクストラ法[ms][/td][td=border:1px solid #ffffff; padding: 0.2em;]ダイクストラ法/ワーシャル-フロイド法[/td][/tr]
[tr=][td=border:1px solid #ffffff; padding: 0.2em;]100[/td][td=border:1px solid #ffffff; padding: 0.2em;]740.107961[/td][td=border:1px solid #ffffff; padding: 0.2em;]1393.678247[/td][td=border:1px solid #ffffff; padding: 0.2em;]1.883074[/td][/tr]
[tr=][td=border:1px solid #ffffff; padding: 0.2em;]200[/td][td=border:1px solid #ffffff; padding: 0.2em;]897.676171[/td][td=border:1px solid #ffffff; padding: 0.2em;]1574.159216[/td][td=border:1px solid #ffffff; padding: 0.2em;]1.753593[/td][/tr]
[tr=][td=border:1px solid #ffffff; padding: 0.2em;]300[/td][td=border:1px solid #ffffff; padding: 0.2em;]1206.441461[/td][td=border:1px solid #ffffff; padding: 0.2em;]2116.898516[/td][td=border:1px solid #ffffff; padding: 0.2em;]1.754663[/td][/tr]
[tr=][td=border:1px solid #ffffff; padding: 0.2em;]400[/td][td=border:1px solid #ffffff; padding: 0.2em;]1707.847925[/td][td=border:1px solid #ffffff; padding: 0.2em;]2995.361072[/td][td=border:1px solid #ffffff; padding: 0.2em;]1.753880[/td][/tr]
[tr=][td=border:1px solid #ffffff; padding: 0.2em;]500[/td][td=border:1px solid #ffffff; padding: 0.2em;]2343.673079[/td][td=border:1px solid #ffffff; padding: 0.2em;]4159.648084[/td][td=border:1px solid #ffffff; padding: 0.2em;]1.774841[/td][/tr][/table]
グラフ
graph.png
実行時間グラフ
graph.png (5.26 KiB) 閲覧数: 165 回
結論
ダイクストラ法をN回実行するプログラムはワーシャル-フロイド法のプログラムに比べ、約1.75倍遅いことがわかる。
全点対最短路には、実装もシンプルなワーシャル-フロイド法を使いましょう。
ページトップ
コメントはまだありません。