C Dijkstraアルゴリズムfloydアルゴリズム拡張07-図6観光計画(25分)

43757 ワード
データ構造 アルゴリズム 図
07-図6観光計画(25分)
ドライブ旅行の路線図があれば、都市間の高速道路の長さと、その道路が受け取る通行料がわかります.相談に来た観光客が出発地と目的地の間の最短経路を探すのを助けるプログラムを書く必要があります.いくつかのパスが最も短い場合は、最も安いパスを出力する必要があります.
入力フォーマット:入力説明:入力データの1行目には4つの正の整数N、M、S、Dが与えられ、ここでN(2≦N≦500)は都市の個数であり、ついでに都市の番号を0~(N−1)と仮定する.Mは高速道路の本数です.Sは出発地の都市番号です.Dは目的地の都市番号です.その後のM行では、都市1、都市2、高速道路長、料金額、中間をスペースで分け、数字はいずれも整数で500を超えない高速道路の情報が与えられる.保証解の存在を入力します.
≪出力フォーマット|Output Format|emdw≫:1行に出力パスの長さと課金総額を、数値間でスペースで区切って、出力の最後に余分なスペースを追加することはできません.
サンプルを入力:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

出力サンプル:
3 40

問題を解く単一ソースの最短パス;最短経路を得る以外に、その上で最も安い経路を得る必要があります.
単一ソースの最短経路をdijkstraアルゴリズムでdijkstraアルゴリズムを使用する場合、隣接マトリクス表示図がより便利である.
こんなに多くの構造関数を設定するのは遅いが、debugとコードの修正はもっと速い.1.図面構造を設定Vertexをroadタイプに変更し、distanceとcostの2つのメンバー変数がある
#include
using namespace std;
typedef struct road Vertex;
typedef int weighttype; 
#define MAX 501
#define INFINITY 65533

struct road{
	int distance;
	int cost;
};

typedef struct  GNode *ptrtoGNode;  //    
struct GNode{
	int Nv;  //   
	int Ne;  //  
	Vertex G[MAX][MAX]; //  500    
	int start;
	int end; 
};
typedef ptrtoGNode MGraph;

2.初期化図関数
MGraph CreateGraph(int n)
{
	MGraph Graph = new struct GNode;
	Graph->Nv=n;
	Graph->Ne=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			Graph->G[i][j].cost=INFINITY;
			Graph->G[i][j].distance=INFINITY;
}
	return Graph;
	//            
 }

3.エッジ構造
typedef struct ENode * ptrtoENode;
struct ENode{
	//   
	int V1;
	int V2;
	weighttype distance;
	weighttype cost; 
};
typedef ptrtoENode Edge;

4.エッジ挿入図における関数標準の無方向挿入法
void InsertEdge(MGraph Graph,Edge E)
{
	Graph->G[E->V1][E->V2].cost=E->cost;
	Graph->G[E->V1][E->V2].distance=E->distance;
	
	Graph->G[E->V2][E->V1].cost=E->cost;
	Graph->G[E->V2][E->V1].distance=E->distance;
}

5.図面作成関数
MGraph BuildGraph()
{
	int N,M,S,D;
	cin>>N;
	 //s  ，d   
	MGraph Graph= CreateGraph(N);
	cin>>Graph->Ne>>Graph->start>>Graph->end;
	if(Graph->Ne!=0)
	for(int i=0;i<Graph->Ne;i++)
	{	
		Edge E=new struct ENode;
		cin>>E->V1>>E->V2>>E->distance>>E->cost;
		InsertEdge(Graph,E);
	}
	return Graph;
}

上のコードは入力操作を行い、図を構築した.MGraph Graph保存を確立できます.次はDijkstra関数で図を処理して出力します.注意点Dijkstra関数は毎回未処理のdistance最小値で処理されます.FindMinDist関数が必要で、sから出発する最小distanceのeの下付き文字を得る.すべての宛先が処理された場合、ERROR値-1を返せばよい.
int FindMinDist(MGraph Graph,int dist[],int collected[])
{
	int MinV,V; //  
	int MinDist = INFINITY;
	
	for(V=0;V<Graph->Nv;V++)
	{	//            
		if(collected[V]==false && dist[V]<MinDist)
		{
			MinDist = dist[V];
			MinV=V; //     
		}
	 }
	 if(MinDist<INFINITY)
	 	return MinV;
	 else return -1; 
 }

Dijkstra関数はまずdistリストを初期化し、sから各都市までの最短距離を表す.costを再初期化し、sから各都市までの最短距離経路に描かれたお金を表す.pathを再初期化し、sから各都市までの最短距離の経路を表す.distはs行の各要素のdistanceに初期化される.无辺则INFINITY;costはs行の各要素のcostに初期化される.无辺则INFINITY;初期化起点距離とcostは、いずれも0であり、自分から自分までの距離が0であり、費用が0であるためである.起点をcollectedに収める.循環を開始します:s行の中で遍歴したことがない都市の下標を得ます;この都市に収入を得る.この都市を各S行都市に循環する距離:他の都市が収録されていない場合、両者の距離1.負のエッジであるかどうかを判断する--負のエッジでは最小値を計算できない--失敗して終了する.(本題は使わない)
	if(dist[V]+Graph->G[V][i].distance

S距離が最も短いVからV-iを通る辺からiまでの距離は現在からiまでの距離より小さい:iを更新する距離も更新するのにかかるお金;パスと(本題はパスを保存する必要はありません).距離が等しい場合は、より小さくても更新します.
bool Dijkstra(MGraph Graph, int s,int e) //S    
{   //   ，dist     ，path   ，s   
	int collected[MAX]; //       
	int V;
	int dist[MAX];
	int cost[MAX];
	int path[MAX];   //     
	
	for(int i=0;i<Graph->Nv;i++)
	{
		dist[i]=Graph->G[s][i].distance;   //  
		cost[i]=Graph->G[s][i].cost;
		if (dist[i]<INFINITY)
			path[i]=s;   //i     s
		else 
			path[i]=-1;   //    
		collected[i]=false;
	 } 
	 
	 dist[s]=0;   //       
	 cost[s]=0;
	 collected[s]=true;
	 
	 while(1)
	 {
	 	V=FindMinDist(Graph,dist,collected);
	 	if(V==-1)
	 		break;
	 	collected[V]=true;
	 	for( int i=0;i<Graph->Nv;i++)
	 		if(collected[i]==false && Graph->G[V][i].distance<INFINITY){
	 			if(Graph->G[V][i].distance<0)
	 				return false; //   ——  
				if(dist[V]+Graph->G[V][i].distance<dist[i])
				{
					dist[i]=dist[V]+Graph->G[V][i].distance; //  dist[i]
					cost[i]=cost[V]+Graph->G[V][i].cost;
					path[i]=V;
				 }
				 //      ，    ； 
				 if(dist[V]+Graph->G[V][i].distance==dist[i]&&cost[V]+Graph->G[V][i].cost<cost[i]){
				 	dist[i]=dist[V]+Graph->G[V][i].distance; //  dist[i]
					cost[i]=cost[V]+Graph->G[V][i].cost;
					path[i]=V;
				 } 
			 }
	 } //while    
	 cout<<dist[e]<<" "<<cost[e]<<endl;
	 return true;
 }

main関数
int main()
{
	MGraph Graph= BuildGraph();
	bool t = Dijkstra(Graph,Graph->start,Graph->end);
	
}

うっかりしてもfloydのアルゴリズムを作って、複雑度が高すぎてタイムアウトしました.建図規範のため、main関数とfloyd関数を変えればいいのです.
void Floyd(MGraph Graph,Vertex D[][MAX]){
	for(int i=0;i<Graph->Nv;i++)
		for(int j=0;j<Graph->Nv;j++)
			D[i][j]=Graph->G[i][j];
			
	for(int k=0;k<Graph->Nv;k++)
		for(int i=0;i<Graph->Nv;i++)
			for(int j=0;j<Graph->Nv;j++)
			{	
				if(D[i][k].distance+D[k][j].distance<D[i][j].distance)
				{
					D[i][j].distance  = D[i][k].distance+D[k][j].distance;
					D[i][j].cost  = D[i][k].cost+D[k][j].cost;
				}
				if(D[i][k].distance+D[k][j].distance==D[i][j].distance
				&&D[i][k].cost+D[k][j].cost<D[i][j].cost)
				{
					D[i][j].distance  = D[i][k].distance+D[k][j].distance;
					D[i][j].cost  = D[i][k].cost+D[k][j].cost;
					}	
			}
}
//   
void output(MGraph Graph)
{
	Vertex D[MAX][MAX];
	Floyd(Graph,D);
	//  D    distance   cost；
	cout<<D[Graph->start][Graph->end].distance<<" "<<D[Graph->start][Graph->end].cost;
	
}

//
int main()
{
	MGraph Graph=BuildGraph();
	output(Graph);
}

この問題をまとめるとdistanceが同じ場合、costの判断が1つ増えた.Dijkstraアルゴリズム:(負のエッジがあれば無効)if(Graph->G[V][W]<0)collectedリストが必要で、最小値が見つかった点を保存します.distリストが必要で、現在の点から他の点までの最短パスを保存し、INFINITYに初期化します.Sからvまでの最短経路を計算する方法は
for(int i=0;iNv;i++)
if(dist[i]+Graph->G[i][V] < dist[V])  dist[V]=dist[i]+Graph->G[i][V] ;

複雑度はO(N^2)であり、最小値を探す複雑度である.最小スタックでO(Nlogn)に下げることができる.
Floydアルゴリズム:(負のコイルがあれば失効する)if(i=j&&D[i][j]<0)を1回転して負の図に値する隣接行列表現に戻す.無辺は最大値INFINITYに初期化される.これに基づいて、2つの点ごとの最短距離が得られる.collectedリストは不要
for(int k=0;kNv;k++)
	for(int i=0;iNv;i++)
		for(int j=0;jNv;j++)
			if(D[i][k]+D[k][j]

呼び出し時——D[n][n]をスキップし、自分から自分の最小値まで0とする.三重サイクルは、各2つの点の最小値を得る--動的計画のある最適サブ問題の継承;複雑度O(N^3);
costを計算する必要がある場合、Dijkstraアルゴリズムはcostリストを追加し、開始点を他の点ごとにcostを保存する必要があります.
観光計画問題の普及:要求数の最短経路は何本ありますか?count[s]=1;もっとショートが見つかった場合:count[W]=count[V];WとVは1辺しか差がないので、両者は同じである.等長路が見つかった場合:count[W]+=count[V];登場路の数はWの前の一点の路の数である.要求辺数が最も少ない最短ルートcount[s]=0;もっとショートが見つかった場合:count[W]=count[V]+1;等長路が見つかった場合:count[W]=count[V]+1;
Laravel Collection型の配列変換 toArray と all の違い
【洛谷】P 1022-川を渡る卒