贪心算法完成单源最短路径程序.
时间: 2024-05-15 12:10:45 浏览: 29
贪心算法是一种常见的算法思想,它通过每一步的最优选择来达到整体的最优解。在单源最短路径问题中,贪心算法的实现思路为从起点开始,每次选择当前离起点最近的未被访问过的点作为下一个路径点,并更新从起点到该点的距离和路径。
具体实现可以采用以下步骤:
1. 初始化距离数组dist和标记数组visited,将起点的dist设置为0,其余点的dist设置为正无穷大,visited设置为false。
2. 循环n次,每次选择一个离起点最近的未被访问过的点v,并标记visited[v]为true。
3. 对于每个v的邻居节点u,如果visited[u]为false且从起点到v再到u的距离小于起点到u的距离,则更新dist[u]和前驱节点pre[u]。
4. 循环结束后,dist数组中存储了起点到各个节点的最短距离,pre数组中存储了最短路径上每个节点的前驱节点。
相关问题
贪心算法的单源最短路径
贪心算法的单源最短路径问题可以通过 Dijkstra 算法来解决。具体来说,该算法维护一个集合 S,表示已经找到最短路径的顶点集合,以及一个数组 dist,表示从源点到各个顶点的最短距离。
算法的基本思想是从源点开始,依次选择距离源点最近的未确定最短路径的顶点,然后更新该顶点的邻居顶点的最短距离。具体实现时,可以使用一个优先队列来保存未确定最短路径的顶点,每次选择距离源点最近的顶点进行更新。更新邻居顶点的最短距离时,如果经过当前顶点可以得到更小的距离,则更新其最短距离,并将其加入到优先队列中。
这样,当所有顶点都被加入到 S 集合中时,dist 数组中保存的就是从源点到所有顶点的最短距离。
用贪心算法解决单源最短路径问题c++
单源最短路径问题可以使用基于贪心算法的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;
}
```