最短路径 Dijkstra算法
程序员文章站
2024-03-16 13:26:10
...
Dijkstra算法,很简单。已从出发点开始,一层层向下搜索,每次选择总路径最短的点为搜索点,继续向下搜索,直到找到终点,且路径最短。
两个测试用例:第一行n,m,s,t,分别代表点的总数,路径的总数,出发点和终点。接下来m行,b, e, l 代表路径的起点,结束点和长度。算法不严谨的地方,可自行修改。
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
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;
}
上一篇: 最短路之Floyd算法
下一篇: Dijkstra算法 最短路径