平均経路長を求めるプログラム

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
RTEM
記事: 5
登録日時: 4年前
住所: 福岡

平均経路長を求めるプログラム

#1

投稿記事 by RTEM » 4年前

今、ネットワークの平均経路長を求めるプログラムを作っています。
ダイクストラ法による下記のプログラムでは総数Nsizeを10000あたりまで大きくすると計算時間が
膨大になってしまうため、より早く求められるようにしたいと考えています。

ー重要な要素は3つー
Network[ノードAのID][ノードBのID]=0:リンクなし,1:リンクあり,-9:A_ID=B_IDのとき
NeighbourID[ノードAのID]=ノードBのID(→Aの友人のi番目がB)
NumLink[ノードAのID]=n(→Aのリンク数はn本)
この3つの情報から平均経路長を短い時間で求めることができる方法、
ご教授願えませんか?

コード:

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <cstring>
#include <cstdlib>
#include <ctype.h>
#include <sstream>
#include <string>
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <functional>

using namespace std;
# define Nsize 10000 //総数
vector <vector<short>> Network;//リンクマトリクス
vector <vector<short>> NeighbourID;//隣人のID
vector <int> NumLink;//次数
vector <vector<short>> Path;

int AverageLink=8;
int AveRoad[Nsize];

/////////////////////////////////統計量初期化///////////////////////////////
void IntVector(){
	
	NumLink.resize(Nsize);
	Network.resize(Nsize);
	NeighbourID.resize(Nsize);
	Path.resize(Nsize);

	for(int i=0; i<Nsize; ++i){
		NumLink[i]=0;
		Network[i].resize(Nsize);
		NeighbourID[i].resize(Nsize);
		Path[i].resize(Nsize);

		for(int j=0; j<Nsize; ++j){
			if(i==j)
				Network[i][j]=-9;
			else
				Network[i][j]=0;
			NeighbourID[i][j]=-9;
			Path[i][j]=0;
		}
	}
}
void Neinformation(){
	for(int i=0; i<Nsize; ++i){
		int k=0;
		NumLink[i]=0;
		for(int j=0; j<Nsize; ++j){
			if(Network[i][j]==1){
				NumLink[i]++;
				NeighbourID[i][k]=j;
				++k;
			}
		}
	}
};
////////////////////PathLength/////////////////////////
double PathLength(){

	int Road[Nsize];//経路長記録
	int s, minLen, f[Nsize]={0};
	double MeanPath=0;
	
	for(int start=0;start<Nsize;start++){
		
		for(int j=0 ; j<Nsize ; j++ ){
			Road[j] = 9999;
			f[j] = 0;
		}
		s=start;	
		Road[s] = 0;
		for(int m=1 ; m<Nsize ; m++ ){
			f[s] = 1;
			for(int j=0 ; j<Nsize ; j++ ){
				if( Network[s][j] != 1 ) continue;
				if( Road[s]+Network[s][j] < Road[j] )
					Road[j]=Road[s]+Network[s][j];
			}
			minLen = 9999;
			for(int j=0 ; j<Nsize ; j++ ){
				if( f[j] == 1 ){
					continue;
				}
				if( Road[j] < minLen ){ 
					minLen = Road[j];
					s = j;
				}
			}
		
		}
		for(int i=0 ; i<Nsize ; i++ ){
			Path[start][i]=Road[i];
			MeanPath+=Road[i];
			AveRoad[start]+=Road[i];
		}
	}//for_Nsize
	
	MeanPath=MeanPath/(Nsize*(Nsize-1));
	return MeanPath;
	
};
//////////サイクルグラフ
void Circle(){
	for(int i=0; i<Nsize; ++i){
		for(int j=0; j<AverageLink/2; ++j){
			if(i+j+1<Nsize){
				Network[i][i+j+1]=1;
				Network[i+j+1][i]=1;
			}
			else{
				Network[i][i+j+1-Nsize]=1;
				Network[i+j+1-Nsize][i]=1;
			}
		}
	}
	Neinformation();

};
///////////// M A I N //////////
int main(){

	IntVector();
	Circle(); 
	cout<<PathLength()<<endl;
	return 0;
};

chop.chop
記事: 36
登録日時: 4年前

Re: 平均経路長を求めるプログラム

#2

投稿記事 by chop.chop » 4年前

無効グラフでダイクストラを用いて遅いとなると、A*を試されてみてはいかがでしょうか?
以前にここの掲示板で素晴らしくわかりやすい解説があるのでどうぞ。
http://dixq.net/forum/viewtopic.php?f=3&t=11030

ダイクストラでの探索対象をゴールに近い順に選んでいく、という点を変えるだけなので上記の//サイクルグラフの処理を少し変えるだけで実装できるかと思います。

RTEM
記事: 5
登録日時: 4年前
住所: 福岡

Re: 平均経路長を求めるプログラム

#3

投稿記事 by RTEM » 4年前

ありがとうございます。
既出だったようで申し訳ないです。
とにかく、実装してみます。

閉鎖

“C言語何でも質問掲示板” へ戻る