用贪心算法解决单源最短路径问题c++
时间: 2024-06-13 20:04:53 浏览: 19
单源最短路径问题可以使用基于贪心算法的Dijkstra算法来解决。下面是解决该问题的步骤:
1. 初始化:将源点到所有其他点的距离初始化为无穷大,将源点到自身的距离初始化为0。
2. 选择:从未确定最短路径的点中选择距离最短的点作为当前点。
3. 更新:更新当前点的邻居节点的距离,如果从源点到当前点的距离加上当前点到邻居节点的距离小于源点到邻居节点的距离,则更新源点到邻居节点的距离。
4. 标记:将当前点标记为已确定最短路径的点。
5. 重复:重复2-4步骤,直到所有点都被标记为已确定最短路径的点。
下面是使用C++实现Dijkstra算法的代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];
int n, m;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, 1});
while (q.size())
{
auto t = q.top();
q.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
q.push({dist[j], j});
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
if (dist[n] == 0x3f3f3f3f) puts("-1");
else cout << dist[n] << endl;
return 0;
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)