求最短路径（Floyd算法和Dijkstra算法）

一、Floyd算法

 

      假设 _vertex[i][j] 表示节点 i 到节点 j 的最短距离，那么在图中遍历其它的点 k 时，如果 _vertex[i][k] + _vertex[k][j] < _vertex[i][j] 时，就对 _vertex[i][j] 进行更新，即 _vertex[i][j] = _vertex[i][k] + _vertex[k][j]，和动态规划的思想一样；

 

     假设 _vertexPath[i][j] 记录节点 i 到节点 j 的路径中最后一个节点，或者说最后一个节点的前一个节点（如果包括正在计算的节点j的话），那么在更新 _vertex 的时候，就可以记录下路径的最后一个节点。

 

代码如下：

 

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;

#define LL long long
#define ULL unsigned long long
#define LOOP( X, Y )  for( int X = 0; X < Y; X++ )

const LL MAX = 999999;

LL nodes = 0, egdes = 0;

void Floyd( vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes );
void PrintPath( int i, int j, vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes );
int main()
{
	cin>>nodes>>egdes;

	vector< vector<int> >_vertex( nodes, nodes );
	vector< vector<int> >_vertexPath( nodes, nodes );

	LOOP( i, nodes )
	{
		LOOP( j, nodes )
		{
			_vertex[i][j] = MAX;    //初始两个节点之间的距离为无穷大
		}
	}

	Floyd( _vertex, _vertexPath, nodes );

	LL start = 0, destinate = 0;

	cin>>start>>destinate;

	PrintPath(start, destinate, _vertex,_vertexPath,nodes);

	return 0;
}

void Floyd( vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes )
{
	LOOP( i, nodes )
	{
		LOOP( j, nodes )
		{
			_vertexPath[i][j] = i;  //初始节点i到节点j的路径最后一个节点为i
		}
	}

	LOOP( i, nodes )
	{
		LOOP( j, nodes )
		{
			LOOP( k, nodes )
			{
				if( _vertex[i][j] > _vertex[i][k] + _vertex[k][j] )
				{
					_vertex[i][j] = _vertex[i][k] + _vertex[k][j]; //更新最短路径的值
					_vertexPath[i][j] = k;   //记录节点i到节点j的最短路径中最后一个节点，或者说最后一个节点的前一个节点（如果包括正在计算的节点j的话）
				}
			}
		}
	}

	return;
}

//输出路径函数，
//参数说明： i ： 表示起始点
//           j ： 表示终点
void PrintPath( int i, int j, vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes )
{
	stack<int> Path;

	if( i != j )   //如果起点和终点不同才输出
	{
		cout<<_vertex[i][j]<<endl;

		LL k = j;

		do
		{
			k = _vertexPath[i][k];
			Path.push(k);      //因为每次存放的是最后一个节点，所以路径是倒着的，所以使用一个栈进行存储，反过来输出。
		}while( k != i );

		cout<<Path.top()+1;

		while( !Path.empty() )
		{
			cout<<"->"<<Path.top()+1;
		}
		cout<<endl;
	}

	return ;
}

 

 

二、Dijkstra算法

 

       设dist[i] 表示点 i 到原点source的最小距离，pass[i] 记录遍历过的点，1表示遍历过得，0表示未遍历，prev[i] 记录第 i 个节点的前一个节点，v[i][j] 表示节点 i 到节点 j 之间的距离，不可达的话，距离为MAX，步骤如下：

 

     1、令u动态地表示起始点，刚开始 u = source，对 dist[i] 进行初始化，u不可到达的点，dist[i] = MAX，可到达的点，则dist[i] = v[u][i]， 同时记录节点 i 的前一个节点prev[i]， 若节点可达，则prev[i] = u，否则prev[i] = -1，最后将 pass[u] = 1，表示原点已经遍历过了。

 

      2、对 u 周围的节点进行遍历，选择出距离节点 u 最短的节点 j ，这时 u = j，更新起始点，将prev[j] = source， 并将 pass[j] = 1；

 

      3、对所有的节点进行遍历，判断 dist[j] > dist[u] + v[u][j] 是否满足，即判断通过节点 u 到达节点 j 是否为最短的，如果满足条件，则对 dist[j] 进行更新，并将prev[j] = u。

 

代码如下：

#include <iostream>
#include <vector>
using namespace std;

#define LL long long 

const LL MAX = 999999999;


void Dijkstra( int nodes, int s, vector<LL> &dist, vector<int> &prev,  vector< vector<int> > v )
{
	vector<bool> passed(nodes);
	for( int i = 0; i < nodes; i++ )
	{
		dist[i] = v[s][i];
		passed[i] = false;   //初始每个节点都未遍历过
		if( dist[i] == MAX )
			prev[i] = -1;
		else
			prev[i] = s;
	}

	dist[s] = 0;      //初始s到s的距离为0
	passed[s] = true; //初始s已经遍历过

//依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
//一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
	for( int i = 1; i < nodes; i++ )
	{
		LL temp = MAX;
		int u = s;

//找出当前未使用的点j的dist[j]最小值
		for( int j = 0; j < nodes; j++ )
		{
			if( (!passed[j]) && dist[j] < temp )
			{
				u = j;
				temp = dist[j];
			}
		}
		passed[u] = true;  //把邻接点中距离最短的点加入到passed中

		更新dist
		for( int j = 0; j < nodes; j++ )
		{
			if( (!passed[j]) && (v[u][j] < MAX)  )
			{
				LL newdist = dist[u] + v[u][j];
				if( newdist < dist[j] )
				{
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}	

	}
}

int main()
{
	freopen("Dijkstra.in", "r", stdin);

	int nodes = 0;
	long long edges = 0;

	cin>>nodes;
	cin>>edges;

	vector< vector<int> >v(nodes,nodes);  //定义邻接矩阵
	vector<LL> dist(nodes);  //记录当前节点到源节点的最短路径长度
	vector<int> prev(nodes);  //记录当前节点的前一个节点

	for( LL i = 0; i < nodes; i++ )
	{
		for( LL j = 0; j < nodes; j++ )
		{
			v[i][j] = MAX;         //初始化将两点之间的距离为MAX
		}
	}

	int p = 0, q = 0, len = 0;
	for( int i = 0; i < edges; i++ )
	{
		cin>>p>>q>>len;
		v[p-1][q-1] = len;
		v[q][p] = len;  //加上这句，表示无向图
	}

	for( int i = 0; i < nodes; i++ )
	{
		dist[i] = MAX;   //初始化每个节点到源节点的路径长度为MAX
	}

	Dijkstra(nodes, 3, dist, prev, v);   //参数：节点个数， 源节点， dist数组，prev数组，v邻接矩阵

	cout << "源点到最后一个顶点的最短路径长度: " << dist[nodes-1] << endl;

	return 0;
}