欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短路径 Dijkstra算法

程序员文章站 2024-03-16 13:26:10
...

Dijkstra算法,很简单。已从出发点开始,一层层向下搜索,每次选择总路径最短的点为搜索点,继续向下搜索,直到找到终点,且路径最短。

两个测试用例:第一行n,m,s,t,分别代表点的总数,路径的总数,出发点和终点。接下来m行,b, e, l 代表路径的起点,结束点和长度。算法不严谨的地方,可自行修改。

最短路径 Dijkstra算法

8 16 1 8
1 6 24
1 3 47
1 5 70
6 4 120
6 3 25
4 8 29
3 4 88
3 2 55
3 7 66
3 5 23
2 4 31
2 8 79
2 7 74
5 2 31
5 7 42
7 8 66

最短路径 Dijkstra算法

9 14 1 9
1 2 5
1 3 3
2 4 1
2 5 3
2 6 6
3 6 7
3 5 8
4 7 3
5 7 5
5 8 2
6 7 6
6 8 6
7 9 4
8 9 3

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
//tdw
using namespace std;

struct SEdge
{
	int			beg;//边的起点
	int			end;//边的终点
	int			length;//边的长度
	SEdge(int _b = 0, int _e = 0, int _l = 0)
	{
		beg = _b;
		end = _e;
		length = _l;
	}
};

struct SLine
{
	int		end;			//某一点
	int		minlength;		//从出发点到该点的最短长度
	bool	bover;//该点是否已超过,可不再考虑
	SLine(int _e = 0)
	{
		end = _e;
		minlength = INT_MAX;
		bover = false;
	}
	bool operator < (SLine _other)
	{
		if( this->bover == _other.bover )
			return minlength < _other.minlength;
		return !this->bover;
	}
};

int Dijkstra(const map<int, vector<SEdge>>& mapEdge, vector<SLine>& vLine,int b,int e,int l)//b	e	l 分别对应以某个点为搜索点,搜索的终点,以及从出发点到搜索点的最短长度
{
	map<int, vector<SEdge>>::const_iterator iter = mapEdge.find(b);
	if (iter != mapEdge.end())
	{
		for (SEdge edge : iter->second)
		{
			for (SLine& line : vLine)
			{
				if( line.end == edge.end )
				{//搜索点的下一个点
					if (line.minlength > edge.length + l)
						line.minlength = edge.length + l;
					break;
				}
			}
		}
		sort(vLine.begin(), vLine.end());//排序,最短的推到第一个位置
		if (vLine[0].end == e)
		{
			return vLine[0].minlength;//找到
		}
		vLine[0].bover = true;//已过去的点,不在考虑
		return Dijkstra(mapEdge, vLine, vLine[0].end, e, vLine[0].minlength);
	}
	return -1;
}
int main()
{
	int n,m,s,t;
	cin >> n >> m >> s >> t;
	int index = 0;
	int b, e, l;
	vector<SEdge>	 vEdge(m);
	while (index < m)
	{
		cin >> b >> e >> l;
		vEdge[index++] = SEdge(b,e,l);
	}
	map<int, vector<SEdge>> mapEdge;//key - beg,val edge		构造关系,某点出发的所有边
	for (SEdge edge : vEdge)
	{
		map<int, vector<SEdge>>::iterator iter = mapEdge.find(edge.beg);
		if (iter == mapEdge.end())
		{
			vector<SEdge> vtemp;
			vtemp.push_back(edge);
			mapEdge.insert(make_pair(edge.beg,vtemp));
		}
		else
		{
			iter->second.push_back(edge);
		}
	}

	vector<SLine> vLine(n+1);//从起点出发,到某一点的最短长度
	for (int i = 0;i <= n;++i)
	{
		vLine[i] = SLine(i);
	}
	
	int res = Dijkstra(mapEdge, vLine, s, t,0);
	cout << res;
	return 0;
}