最短パス-DijkstraアルゴリズムとFloydアルゴリズム

8669 ワード
データ構造とアルゴリズム
一、最短経路概念
図中の1つの頂点から別の頂点には複数のパスが存在する可能性があり、各パスが通過するエッジの数が異なる可能性があり、各パスが通過するエッジの重み値が異なる可能性があります.最小のパスを2つの頂点の最短パスにします.
最短経路に関する2つの一般的なアルゴリズム:ディックストラ(Dijstra)アルゴリズムとフロイド(Floyd)アルゴリズム.Dijstraアルゴリズムは、図中の1つの頂点から他のすべての頂点への最短距離と経路を迅速に求めるために使用され、Floydアルゴリズムは、図中の各頂点の最短経路を求めるために使用される.
二、応用
最短経路問題は地図ナビゲーション,道路建設,ルータアドレスなど多くの分野に応用されている.
三、DijstraアルゴリズムとFloydアルゴリズムの具体的な実現
(1)Dijstraアルゴリズム
Dijstraアルゴリズムの基本思想は,図中の頂点集合を2つのグループに分け,第1のグループは最短経路が求められた頂点集合S,第2のグループは残りの最短経路が確定していない頂点集合Uである.次に、既知の頂点kからkに最も近い頂点iminを探索し、頂点iminを第1の頂点セットSのセットに追加し、頂点iminを中間点として他の頂点までの距離がより短い場合、iminの最も経路の中間点を設定し、kから他の頂点までの最短距離を更新し、すべての頂点がセットSに加わるまで、最も近い頂点iminを繰り返し探索する.
次の手順に従います.
①図中の頂点集合を2つのグループに分け、第1のグループは最短経路が求められた頂点集合S、第2のグループは残りの最短経路が確定していない頂点集合Uである.
②既知の開始点kをSに加え、kから他の頂点までの最短距離を図に関連するエッジへの重み値として初期化する(エッジが存在しない場合、距離を無限大に設定する).
③全ての頂点が集合Sに加わるまで、手順④を繰り返す.
④kに最も近い頂点iminを探し、頂点iminを第1群の頂点集合Sに加え、頂点iminを中間点として他の頂点までの距離がより短い場合、iminの最も経路の中間点を設定し、kから他の頂点までの最短距離を更新する.
C++コード実装:
図の隣接行列宣言:
#define N 100

typedef char ElemType;

/*
        
*/
typedef struct _MGraph
{
	int edges[N][N]; //   
	int n; //   
}MGraph;

Dijstraアルゴリズム:
/*
       
g       
k       
path[i]   i         
dis[i]   k     i     
*/
void Dijkstra(MGraph &g, int k, int path[], int dis[])
{
	int* visited = new int[g.n](); //          ，    0
	for (int i = 0; i < g.n; i++) 
	{
		dis[i] = g.edges[k][i]; //         
		path[i] = k; //       
	}
	visited[k] = 1;
	dis[k] = 0;
	for (int cnt = 1; cnt < g.n; cnt++) //  n-1 
	{
		int imin = -1; //        
		for (int i = 0; i < g.n; i++) //          
		{
			if (!visited[i] && (imin == -1 || dis[i] < dis[imin])) 
				imin = i;
		}
		visited[imin] = 1;
		for (int i = 0; i < g.n; i++) //                ，         
		{
			if (!visited[i] && dis[imin] + g.edges[imin][i] < dis[i])
			{
				dis[i] = dis[imin] + g.edges[imin][i];
				path[i] = imin;
			}
		}
	}
	delete[] visited; //      
}

Dijstraアルゴリズムに基づいて生成されたpath配列出力パス:
/*
          k     
*/
void DisplayPath(int k, int path[])
{
	stack s;
	while (path[k] != k)
	{
		s.push(k);
		k = path[k];
	}
	s.push(k);
	int cnt = 0;
	while (!s.empty())
	{
		if (cnt++ > 0) cout << "->";
		cout << s.top();
		s.pop();
	}
	cout << endl;
}

Dijstraアルゴリズムは二重forループを含み,その時間的複雑さはO(n)である.²).
(2)Floydアルゴリズム
Floydアルゴリズムの基本思想は、頂点iから頂点jまでの最短経路長を1つの2次元配列disで保存することであり、dis[i][j]=g.edges[i][j]は頂点jまでの最短経路長を表し、dis配列は図の隣接行列配列dis[i][j]=g.edges[i][j]に初期化される.頂点k=0からkを中間ノードとし、頂点iがkで最も中間ノードが頂点jに到達する距離がより短い場合、kを中間ノードとし、iからjへの最短パスを更新する.kの値に1を加え、すべての頂点が中間ノードと仮定されるまで中間ノードを繰り返し選択します.
次の手順に従います.
①頂点iから頂点jまでの最短経路長を1つの2次元配列disで保持する.すなわち、dis[i][j]は頂点iから頂点jまでの最短経路長を表し、dis配列は図の隣接行列配列dis[i][j]=g.edges[i][j]に初期化される.
②頂点k=0からkを中間ノードと仮定し、③すべての頂点が中間ノードと仮定されるまで手順を繰り返す.
③頂点iがkで最も中間ノードが頂点jに到達する距離がより短い場合は、kを中間ノードとし、iからjへの最短経路を更新する.
C++コード実装:
Floydアルゴリズム:
/*
      
g       
dis[i][j]    i   j       
path[i][j]    j      
*/
void Floyd(MGraph& g, int dis[][N], int path[][N])
{
	for (int i = 0; i < g.n; i++)
	{
		for (int j = 0; j < g.n; j++)
		{
			dis[i][j] = (i == j ? 0 : g.edges[i][j]); //       
			path[i][j] = i; //       
		}
	}
	for (int k = 0; k < g.n; k++)
	{
		for (int i = 0; i < g.n; i++)
		{
			for (int j = 0; j < g.n; j++)
			{
				if (dis[i][k] + dis[k][j] < dis[i][j]) //   K        ，           
				{
					dis[i][j] = dis[i][k] + dis[k][j];
					path[i][j] = path[k][j];
				}
			}
		}
	}
}

Floydによって生成されたpath配列から最短パスを出力:
/*
           
*/
void DisplayPath(int n, int path[][N], int dis[][N])
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << i << "-" << j << "      ：" << dis[i][j] << "     ：";
			DisplayPath(j, path[i]);
		}
	}
}

Floydアルゴリズムは3重forループを含み,その時間的複雑さはO(n)であった.³),各頂点をソースポイントとしてDijstraアルゴリズムを呼び出す時間的複雑さに相当するが,Floydアルゴリズムコードの実現は簡単である.
四、テスト
質問:
頂点0から他の頂点までの最短パス長と最短パス、および各頂点の最短パス長と最短パスを求める方向図を入力します.
サンプル入力:
        4 8        0 1 5        0 3 7        1 2 4        1 3 2        2 0 3        2 1 3        2 3 2
        3 2 1
サンプル出力:
0-0最短経路長:0最短経路長:0-1最短経路長:5最短経路長:0->1 0-2最短経路長:8最短経路:0->3->2 0-3最短経路長:7最短経路:0->3 0-0最短経路長:0最短経路:0-1最短経路長:5最短経路:0->10-2最短経路長:8最短経路:0->3->2 0-3最短経路長:7最短経路:0->3 1-0最短経路長:6最短経路:1->3->2->0 1-1最短経路長:0最短経路:1-2最短経路長:3最短経路:1->3->2-3最短経路長:2最短経路長::1->3 2-0最短パス長:3最短パス長:2->0 2-1最短パス長:3最短パス長:2->1 2-2最短パス長:0最短パス長:2-3最短パス長:2最短パス長:2->3-0最短パス長:4最短パス長:3->2->0 3-1最短パス長:4最短パス長:3->2->1 3-2最短経路長:1最短経路:3->2 3-3最短経路長:0最短経路:3
#include 
#include 
using namespace std;

#define N 100

typedef char ElemType;

/*
        
*/
typedef struct _MGraph
{
	int edges[N][N]; //   
	int n; //   
}MGraph;

/*
       
g       
k       
path[i]   i         
dis[i]   k     i     
*/
void Dijkstra(MGraph &g, int k, int path[], int dis[])
{
	int* visited = new int[g.n](); //          ，    0
	for (int i = 0; i < g.n; i++) 
	{
		dis[i] = g.edges[k][i]; //         
		path[i] = k; //       
	}
	visited[k] = 1;
	dis[k] = 0;
	for (int cnt = 1; cnt < g.n; cnt++) //  n-1 
	{
		int imin = -1; //        
		for (int i = 0; i < g.n; i++) //          
		{
			if (!visited[i] && (imin == -1 || dis[i] < dis[imin])) 
				imin = i;
		}
		visited[imin] = 1;
		for (int i = 0; i < g.n; i++) //                ，         
		{
			if (!visited[i] && dis[imin] + g.edges[imin][i] < dis[i])
			{
				dis[i] = dis[imin] + g.edges[imin][i];
				path[i] = imin;
			}
		}
	}
	delete[] visited; //      
}

/*
          k     
*/
void DisplayPath(int k, int path[])
{
	stack s;
	while (path[k] != k)
	{
		s.push(k);
		k = path[k];
	}
	s.push(k);
	int cnt = 0;
	while (!s.empty())
	{
		if(cnt++ > 0) cout << "->";
		cout << s.top();
		s.pop();
	}
	cout << endl;
}

/*
      
g       
dis[i][j]    i   j       
path[i][j]    j      
*/
void Floyd(MGraph& g, int dis[][N], int path[][N])
{
	for (int i = 0; i < g.n; i++)
	{
		for (int j = 0; j < g.n; j++)
		{
			dis[i][j] = (i == j ? 0 : g.edges[i][j]); //       
			path[i][j] = i; //       
		}
	}
	for (int k = 0; k < g.n; k++)
	{
		for (int i = 0; i < g.n; i++)
		{
			for (int j = 0; j < g.n; j++)
			{
				if (dis[i][k] + dis[k][j] < dis[i][j]) //   K        ，           
				{
					dis[i][j] = dis[i][k] + dis[k][j];
					path[i][j] = path[k][j];
				}
			}
		}
	}
}

/*
           
*/
void DisplayPath(int n, int path[][N], int dis[][N])
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << i << "-" << j << "      ：" << dis[i][j] << "     ：";
			DisplayPath(j, path[i]);
		}
	}
}

int main()
{
	MGraph g;
	while (cin >> g.n)
	{
		for (int i = 0; i < g.n; i++)
			for (int j = 0; j < g.n; j++)
				g.edges[i][j] = INT16_MAX;
		int m, u, v, w;
		cin >> m;
		while (m-- > 0)
		{
			cin >> u >> v >> w;
			g.edges[u][v] = w;
		}
		//Dijkstra
		{
			int* path = new int[g.n];
			int* dis = new int[g.n];
			Dijkstra(g, 0, path, dis);
			for (int i = 0; i < g.n; i++)
			{
				cout << 0 << "-" << i << "      ：" << dis[i] << "     ：";
				DisplayPath(i, path);
			}
			delete[] path, dis;
		}
		//Floyd
		{
			int path[N][N], dis[N][N];
			Floyd(g, dis, path);
			DisplayPath(g.n, path, dis);
		}
	}
	return 0;
}

参考文献
[1]李春葆.データ構造のチュートリアル清華大学出版社、2013.
token bucketアルゴリズムの実現について話します
g 729コーデックのまとめ