最短路-Dijkstra算法整理
2024-10-08 01:17:19
维基说的很全面:https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
理解:
先设置访问数组vis[]和距离数组dist[],开始时把源点(source)先加入已访问数组(vis[source]=1),源点到源点的距离数组设为0(dist[source]=0);然后其它点到源点的dist[]为源点到该点的距离。然后找与源点相连的最近的点,并将其加入访问数组,再用这个点利用松弛操作更新其它未访问的点。循环执行顶点数-1次结束。
下面代码假设源点为1,终点为N。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = ;
int matrix[maxn][maxn];
int vis[maxn], dist[maxn];
int N, M; void Dijkstra(int source)
{
memset(vis, , sizeof(vis));
vis[source] = ;
for (int i = ; i <= N; i++) dist[i] = matrix[source][i]; int cost, k;
for (int i = ; i < N; i++)
{
cost = INF;
for (int j = ; j <= N; j++)
{
if (!vis[j] && dist[j]<cost)
{
cost = dist[j];
k = j;
}
} vis[k] = ; for (int j = ; j <= N; j++)
{
if (!vis[j] && matrix[k][j] != INF&&dist[j]>matrix[k][j] + cost)
{
dist[j] = matrix[k][j] + cost;
}
} }
} int main()
{
while (scanf("%d%d", &N, &M))
{
for (int i = ; i <= N; i++)
for (int j = ; j <= N; j++)
if (i == j) matrix[i][j] = ;
else matrix[i][j] = INF; for (int i = ; i<M; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
matrix[u][v] = matrix[v][u] = w;
}
Dijkstra();
printf("%d\n", dist[N]);
}
return ;
}
用优先队列和vector:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=;
struct Node
{
int num,dis;//num存储当前节点的编号,dis存储路径长度
Node(){}
Node(int a,int b){num=a;dis=b;}
bool operator < (const Node& rhs)const{
dis>rhs.dis;
}
};
priority_queue<Node>que;
vector<vector<Node> >v;
int vis[maxn],dist[maxn];
int N,M; void Dijkstra(int s)
{
for (int i=;i<=N;i++) dist[i]=INF;
dist[s]=;
que.push(Node(s,dist[s]));
while(!que.empty())
{
Node p=que.top();que.pop();
for (int i=;i<v[p.num].size();i++)
{
Node q;
q.num=v[p.num][i].num;
if(dist[q.num]>dist[p.num]+v[p.num][i].dis)
{
dist[q.num]=dist[p.num]+v[p.num][i].dis;
que.push(Node(q.num,dist[q.num]));
}
}
}
} int main()
{
scanf("%d%d",&N,&M);
v.clear();
v.resize(N+);
for (int i=;i<M;i++)
{
int fr,to,w;
scanf("%d%d%d",&fr,&to,&w);
v[fr].push_back(Node(to,w));
v[to].push_back(Node(fr,w)); }
Dijkstra();
printf("%d\n",dist[N]);
}
以hdu1874畅通工程续为例,一个pair较为偷懒的写法:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = ;
vector<pair<int, int> > E[maxn];
int d[maxn];
int n, m; void Dijkstra(int s)
{
priority_queue<pair<int, int> >Q;
d[s] = ;
Q.push(make_pair(-d[s],s));
while (!Q.empty())
{
int now = Q.top().second; Q.pop();
for (int i = ; i < E[now].size(); i++)
{
int v = E[now][i].first;
if (d[v] > d[now] + E[now][i].second)
{
d[v] = d[now] + E[now][i].second;
Q.push(make_pair(-d[v], v));
}
}
}
} int main()
{
while (scanf("%d%d",&n,&m)==)
{
for (int i = ; i < n; i++) E[i].clear();
for (int i = ; i < n; i++) d[i] = 1e9;
for (int i = ; i < m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
E[x].push_back(make_pair(y,z));
E[y].push_back(make_pair(x, z));
}
int s, t;
scanf("%d%d", &s, &t);
Dijkstra(s);
if (d[t] == 1e9)
printf("-1\n");
else
printf("%d\n", d[t]);
}
return ;
}
最新文章
- c#中文件与二进制流文件的转换
- js插件添加打印功能
- 11.2---字符串数组排序,删除变位词(CC150)
- Divide and Conquer:Monthly Expense(POJ 3273)
- 7.7 使用rollup子句
- KindEditor4.1.10,支持粘贴图片(转载!)
- CheckStyle, 强制你遵循编码规范
- Java虚拟机详解03----常用JVM配置参数
- poj1142.Smith Number(数学推导)
- linux内核交互,设备驱动控制管理接口
- C#数据绑定中,时间为空时显示时间为原始日期问题
- Java进阶01 String类
- expdp导出文件,ORA-01555: 快照过旧: 回退段号 716
- POJ 2482 Stars in Your Window(线段树)
- hdu1995 汉诺塔V
- Linux根文件系统介绍
- python 环境变量设置PYTHONPATH
- (转载)CPU、内存、硬盘、指令以及他们之间的关系
- DotNetty 实现 Modbus TCP 系列 (二) ModbusFunction 类图及继承举例
- Flume Source 实例