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

[RTEM]

今、ネットワークの平均経路長を求めるプログラムを作っています。
ダイクストラ法による下記のプログラムでは総数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]

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

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

[RTEM]

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