现在的位置: 首页 > 综合 > 正文

dijkstra算法分析和实现

2018年02月11日 ⁄ 综合 ⁄ 共 1498字 ⁄ 字号 评论关闭

dijkstra算法是解决源节点和目的节点两个之间的最短距离问题。

其实对这个算法并不熟悉,前几天通过在网上查资料后决定自己实现这个算法,也不知道我理解的对不对。。如果不对,希望帮我指出,谢谢。


/*
dijkstra算法思想:定义两个集合S,T。S初始化为源节点,T初始化为其他所有节点,每次在T中找出到源节点中的最短距离。这样就满足一个
				 特性:源节点到S中的任何一个元素的距离比源节点到T中任何一个元素的距离小。当找出这样一个节点后,将其加入到S中,
				 从T中删除这个节点同时更新和源节点到这个节点相连的所有节点的距离(其实不用更新已经在S中的节点)。

				 一直搜索直到找到了这个元素,而不用继续搜索还没有加入到S中的元素(原因就是那个特性)

  我的实现只是用了一个bool isInS[MAX]数组来区分这两个集合,为true是在S,否则是在T中。
*/

#include<iostream>
using namespace std;

#define MAX 1024

int D[MAX][MAX];//记录任何两个节点的距离
bool isInS[MAX];
int pre[MAX];//记录这个最短路径序列。

int findThePath(int start,int end,int nodes)
{
	int current=start;
	isInS[start]=true;
	pre[start]=-1;
	int i;
	while(1)
	{
		int min=MAX;
		for(i=0;i<nodes;i++)//在T中找出到源节点中的最短距离
		{
			if(i!=start&&!isInS[i])
			{
				if(min>D[start][i])
				{
					min=D[start][i];
					current=i;
				}
				
			}
		}
		if(current==end)
			break;
		isInS[current]=true;
		for(i=0;i<nodes;i++)//更新和源节点到这个节点相连的所有节点的距离
		{
			if(i!=current&&!isInS[i]&&D[current][i]!=MAX)
			{
				if(D[start][i]>D[start][current]+D[current][i])
				{
					D[start][i]=D[start][current]+D[current][i];
					pre[i]=current;
				}
			}
		}
	}
	
	int ret=0;
	cout<<"最短路径序列为:	";
	while(pre[current]!=-1)
	{
		ret+=D[pre[current]][current];
		cout<<current<<"	";
		current=pre[current];
	}
	cout<<current<<endl;
	return ret;
	
}

void main()
{
	int nodes,edges;
	int firstnode,secondnode,dis;
	int i,j;
	int minPath;
	while(1)
	{
		cin>>nodes>>edges;
		for(i=0;i<nodes;i++)
			for(j=0;j<nodes;j++)
			{
				if(i==j)
					D[i][j]=0;
				else
					D[i][j]=MAX;		
			}
		memset(isInS,false,nodes);
		memset(pre,0,nodes*4);
		for(i=0;i<edges;i++)
		{
			cin>>firstnode>>secondnode>>dis;
			D[firstnode][secondnode]=dis;
			D[secondnode][firstnode]=dis;
		}
		minPath=findThePath(0,3,4);
		cout<<"最小路径:	"<<minPath<<endl;
	}
}


抱歉!评论已关闭.