最短路之 \(dijekstra\) 学习笔记
复习 \(dijekstra!\)
怎么说,就写一下 \(dij\) 的实现过程吧
\(dij\) 的思路就是,
将结点分成两个集合:已确定最短路长度的点集(记为$ S$集合)的和未确定最短路长度的点集(记为 $ T$ 集合)。一开始所有的点都属于 $ T $ 集合。
初始化 $dis(s)= 0 $ ,其他点的 $dis $ 均为 $+ \infty $。
然后重复这些操作:
- 从$ T $ 集合中,选取一个最短路长度最小的结点,移到 $ S $ 集合中。
- 对那些刚刚被加入 $S $ 集合的结点的所有出边指向的点更新距离并放入队列。
直到 $T $ 集合为空,算法结束。
把图上的点分成两个集合,一个是已经确定最短路的集合 \(S\) 和剩下的点 \(S'\)
同时用一个优先队列 \(Q\) 来维护与 \(S\) 中的点相邻的点中到起点 \(s\) 的目前的最短距离(这个地方用 \(pair\) 来同时存距离和点的编号)
然后实现步骤就是
每次取出 \(Q\) 的队头也就是目前不在 \(S\) 之中到起点 \(s\) 距离最近的点 \(i\)
如果这个点之前没被取出来过,也就是没被标记过,不在 \(S\) 之中
则将其标记,也就是放到 \(S\) 中 然后依次遍历 \(i\) 点的所有相邻的节点 \(t\)
如果 \(t\) 不在 \(S\) 之中 且 \(dis(s,i)+dis(i,t)<dis(s,t)\) 的话,就将 \(t\) 放到 \(Q\) 中
当 \(Q\) 重新变为空时,最短路就求好了
时间复杂度
\(O(m\log n+nk\log n) \approx O(m\log n)\)
其中k为每个点的平均邻居数
代码如下
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
struct edge
{
int f, t;
int w;
};
edge edges[1000000];
struct node
{
bool done;
int dis = 1099999999;
vector<int> to;
int num;
void clear()
{
this->done = 0;
this->dis = 2147483647;
}
};
node nodes[300000];
//第一关键字是距离,第二关键字是节点编号
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
void dij(int start_)
{
int the_bian, the_dis, temp_dis, to_;
q.push({0, start_});
nodes[start_].dis = 0;
while (!q.empty())
{
pair<int, int> the_node = q.top();
q.pop();
the_dis = the_node.first;
the_bian = the_node.second;
if (!nodes[the_bian].done)
{
nodes[the_bian].done = 1;//标记,放入S中
for (int yy = 0; yy < nodes[the_bian].to.size(); yy++)//便利这个点的所有出边
{
to_ = edges[nodes[the_bian].to[yy]].t;
temp_dis = nodes[the_bian].dis + edges[nodes[the_bian].to[yy]].w;
if (temp_dis < nodes[to_].dis)
{
nodes[to_].dis=temp_dis;//更改距离
q.push({temp_dis, to_});//入队
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m >> k;
int aa, bb, cc;
for (int ww = 1; ww <= m; ww++)
{
cin >> aa >> bb >> cc;//建边
edges[ww].f = aa;
edges[ww].t = bb;
edges[ww].w = cc;
// edges[ww + m].f = bb;
// edges[ww + m].t = aa;
// edges[ww + m].w = cc;
nodes[aa].to.push_back(ww);
// nodes[bb].to.push_back(ww + m);
}
dij(k);
for (int yy = 1; yy <= n; yy++)
{
cout << nodes[yy].dis << " ";
}
return 0;
}
标签:int,短路,笔记,ww,edges,dijekstra,bian,nodes,dis
From: https://www.cnblogs.com/sea-and-sky/p/18414446