学习记录：Dijstra最短路
其实Dijstra早学过，这次主要写点用邻接表和堆优化的东西
想法
Dijstra的想法其实很简单，维护一个已经达到最短路线的点的集合即可。
从出发点开始，找到距离出发点最近的那个点加入集合，重复此步骤直至所有点都加入集合即可。
原因很简单，设出发点为\(s\)，距离\(s\)最近的点是\(i\)，\(Dis[i]<Dis[其他点]+其他点到点i的距离\)，因此最近的点就加入集合了。
邻接矩阵实现的Dijstra
最简单的Dij，但是过不了[洛谷弱化版的模板题][https://www.luogu.com.cn/problem/P3371]，空间占用大，但是方便理解Dij的思路
int Map[maxn][maxn];
int vis[maxn];
ll dis[maxn];
int n, m, s;
void Dij()
{
for (int i = 1; i <= n; i++)
dis[i] = Map[s][i];
dis[s] = 0;
vis[s] = 1;
for (int j = 1; j <= n; j++)
{
int flag = 0;
for (int i = 1; i <= n; i++)
if (!vis[i] && (dis[i] < dis[flag] || flag == 0))
flag = i;
vis[flag] = 1;
for (int i = 1; i <= n; i++)
if (!vis[i])
dis[i] = min(dis[i], dis[flag] + Map[flag][i]);
}
}
int main()
{
cin >> n >> m >> s;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
Map[u][v] = min(w, Map[u][v]);//洛谷的数据最坑的就是有重边...
}
Dij();
for (int i = 1; i <= n; i++)
cout << dis[i] << ‘ ‘;
return 0;
}
邻接表实现的Dijstra
这样就可以过模板题了。用的vector实现。
struct node
{
int to, val;
node(int to, int val) : to(to), val(val) {}
};
ll n, m, s;
ll dis[maxn];
int vis[maxn];
vector<node> Map[maxn];
void Dij()
{
for (int i = 0; i <= n; i++)
dis[i] = INF;
dis[s] = 0;//这里没有初始化dis数组，是因为接下来的循环可以直接初始化
for (int k = 0; k < n; k++)
{
int kk = 0;
for (int i = 1; i <= n; i++)
if (!vis[i] && dis[i] < dis[kk])
kk = i;
vis[kk] = 1;
for (int i = 0; i < Map[kk].size(); i++)
if (dis[Map[kk][i].to] > dis[kk] + Map[kk][i].val)
dis[Map[kk][i].to] = dis[kk] + Map[kk][i].val;
}
}
int main()
{
cin >> n >> m >> s;
for (int i = 0, a, b, c; i < m; i++)
{
cin >> a >> b >> c;
Map[a].push_back(node(b, c));
}
Dij();
for (int i = 1; i <= n; i++)
cout << dis[i] << ‘ ‘;
return 0;
}
堆优化的Dijstra
struct node
{
int to, val;
node(int to, int val) : to(to), val(val) {}
};
int n, m, s;
vector<node> Map[maxn];
int vis[maxn], dis[maxn];
typedef pair<int, int> P;
void Dij()
{
priority_queue<P, vector<P>, greater<P>> q;
MS(dis, INF);
dis[s] = 0;
q.push(P(0, s));
while (!q.empty())
{
P p = q.top();
q.pop();
int index = p.second;
if (dis[index] < p.first)
continue;
for (int i = 0; i < Map[index].size(); i++)
{
node e = Map[index][i];
if (dis[e.to] > dis[index] + e.val)
{
dis[e.to] = dis[index] + e.val;
q.push(P(dis[e.to], e.to));
}
}
}
}
int main()
{
cin >> n >> m >> s;
for (int i = 1, x, y, z; i <= m; i++)
{
cin >> x >> y >> z;
Map[x].push_back(node(y, z));
}
Dij();
for (int i = 1; i <= n; i++)
cout << dis[i] << ‘ ‘;
return 0;
}