312
127
ACM程序设计 篇一：ACM图论算法：最短路
2021-01-20 21:25:08
1点赞
2收藏
0评论
Floyd(佛洛依德算法)
三个for暴力循环 O(n^3)
for(ll k=1;k<=节点数;k++)
{
for(ll i=1;i<=节点数;i++)
{
for(ll j=1;j<=节点数;j++)
{
if(a[i][k]+a[k][j]<a[i][j])
{
a[i][j]=a[i][k]+a[k][j];
}
}
}
}
Dijkstra(迪杰斯特拉算法) O(nlogn)
与Floyd不同，需要暴力枚举出所有边的情况，Dijkstra通过松弛来实现，松弛最著名的理论就是三角形的任意两边之和大于第三边，即每次找一个与起点最近的点，对这个点连接的边进行松弛；
用结构体+链式前向星存边，关键步骤的本质是bfs，可以用C++ STL的堆来进行优化，通常都使用Dijkstra，但是不适合使用在存在负权值的题目，会造成死循环。
tip：优先队列(priority_queue)，push进去，会自动按照降序的方式插入，因此需要利用重载符(operator)将降序的方式改成升序
'''
void dij()
{
//默认dis数组的值均为0x3f3f3f3f(最大值)
for(ll i=0;i<=n;i++)
{
dis[i]=inf;
}
dis[s]=0;//起点到起点的距离为0
priority_queue<node> q;
q.push({0,s});
while(!q.empty())
{
ll u=q.top().index;
ll d=q.top().w;
q.pop();
if(dis[u]<d)continue;
//如果队列里面的这个点到起点的距离比dis数组里面当前这个点到起点的距离大,则continue
//也可以用vis数组代替
//以下为链式前向星，对每一个点进行遍历
for(ll i=head[u];i!=-1;i=e[i].next)
{
ll v=e[i].to;
if(dis[v]>e[i].w+dis[u])
{
dis[v]=e[i].w+dis[u];
q.push({dis[v],v});
}
}
}
}
'''
向我的偶像迪杰斯特拉致敬
