spfa(链式前向星)+dijkstra(链式前向星)
全栈程序员站长
发布于 2022-11-17 02:32:07
发布于 2022-11-17 02:32:07
代码可运行
运行总次数：0
代码可运行
大家好，又见面了，我是你们的朋友全栈君。
链式前向星
链式前向星可以存图， 它存图的方式是： 将 任 意 一 个 节 点 的 所 有 临 边 按 输 入 顺 序 依 次 连 接 起 来 将任意一个节点的所有临边按输入顺序依次连接起来 将任意一个节点的所有临边按输入顺序依次连接起来 然 后 头 节 点 ( 数 组 ) 存 的 是 最 后 一 个 临 边 的 地 址 然后头节点(数组)存的是最后一个临边的地址 然后头节点(数组)存的是最后一个临边的地址
int head[maxn];//head[i]中i是u->v中的u，head[i]存的是这个头节点对应的最后临边的地址
int cnt//cnt是edge[cnt]中edge的地址
struct node{
int w;//u->v中的边权
int e;//u->v中的v
int next;//就是用next让这个头节点下面的全部临边相连
}edge[maxn];void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].e=v;
edge[cnt].next=head[u];//就是这一步让这个头节点下面的全部临边相连
head[u]=cnt++;
}#include<bits/stdc++.h>
using namespace std;
#define MAXN 100501
struct NODE{
int w;
int e;
int next;
}edge[MAXN];
int cnt;
int head[MAXN];
void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].e=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int main(){
memset(head,0,sizeof(head));
cnt=1;
int n;
cin>>n;
int a,b,c;
while(n--){
cin>>a>>b>>c;
add(a,b,c);
}
int start;
cin>>start;
for(int i=head[start];i!=0;i=edge[i].next)
cout<<start<<"->"<<edge[i].e<<" "<<edge[i].w<<endl;
return 0;
}深度理解链式前向星 https://blog.csdn.net/acdreamers/article/details/16902023
spfa
我 理 解 s p f a 是 在 图 上 跑 的 可 回 头 的 b f s 我理解spfa是在图上跑的可回头的bfs 我理解spfa是在图上跑的可回头的bfs
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<math.h>
#include<vector>
#include<iostream>
#define INF 0x3f3f3f3f
#define ll long long
#define N 100000+10
using namespace std;
int n,m;
int x,y,z;
struct node
{
int y,z;
};
vector<node> mp[1000];
int spfa(int b,int e)
{
bool color[1000];
int d[1000];
memset(color,0,sizeof(color));
memset(d,INF,sizeof(d));
d[b]=0;
queue<int>q;
q.push(b);
color[b]=1;
while(!q.empty())
{
int st=q.front();
q.pop();
color[st]=0;//这里就是和bfs的唯一区别，bfs没有这里，所以color表示的就是这个点有没有进过，进过就不用进了
//spfa里color表示的是队列里有没有st，要是有的话就不用进了
for(int i=0;i<mp[st].size();i++)
{
if(d[st]+mp[st][i].z<d[mp[st][i].y])
{
d[mp[st][i].y]=d[st]+mp[st][i].z;
if(!color[mp[st][i].y])
{
q.push(mp[st][i].y);
color[mp[st][i].y]=1;
}
}
}
}
return d[e];
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
mp[x].push_back((node){
y,z});
mp[y].push_back((node){
x,z});
}
cout<<spfa(1,n)<<endl;
}SPFA详解 https://blog.csdn.net/hlg1995/article/details/70242296
spfa（链式前向星）
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<math.h>
#include<vector>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f
#define maxn 10010
struct node{
int w;
int e;
int next;
}edge[maxn];
int cnt,t,n;
int head[maxn];
void init(){
memset(head,0,sizeof head);
cnt=1;
}
void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].e=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int spfa(){
queue<int> q;
bool color[maxn];
int d[maxn];
memset(d,INF,sizeof d);
memset(color,true,sizeof color);
q.push(1);
d[1]=0;
color[1]=false;
while(!q.empty()){
int st=q.front();
q.pop();
color[st]=true;
for(int i=head[st];i!=0;i=edge[i].next){
if(d[st]+edge[i].w<d[edge[i].e]){
d[edge[i].e]=d[st]+edge[i].w;
if(color[edge[i].e]){
q.push(edge[i].e);
color[edge[i].e]=false;
}
}
}
}
return d[n];
}
int main(){
while(~scanf("%d %d", &t, &n)){
init();
int u,v,w;
for(int i=0;i<t;i++){
scanf("%d %d %d", &u, &v, &w);
add(u,v,w);
add(v,u,w);
}
printf("%d\n", spfa());
}
return 0;
}dijkstra
我 理 解 d i j k s t r a 实 际 上 是 B F S + 贪 心 我理解dijkstra实际上是BFS+贪心 我理解dijkstra实际上是BFS+贪心
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#define INF 0x3f3f3f
#define maxn 1005
using namespace std;
int n;
vector< pair<int,int> >mp[maxn];
int dijkstra(int b,int e){
priority_queue< pair<int,int> > p;//有限队列存最小节点（默认优先级较大）
int d[maxn];//用于记录起点s到v的最短路
memset(d,INF,sizeof(d));
d[b]=0;
p.push(make_pair(0,b));//起点
while(!p.empty()){
pair<int,int> f = p.top();
p.pop();
int u=f.second;
if(d[u] < f.first*(-1)) continue;
for(int j=0; j<mp[u].size(); j++){
int v=mp[u][j].first;
if(d[v]>d[u]+mp[u][j].second){
d[v]=d[u]+mp[u][j].second;
p.push(make_pair(d[v]*(-1),v));// priority_queue（默认优先级较大）所以要*-1；
}
}
}
return d[e];
}
int main(){
cin>>n;
int k,c,u,v;
for(int i=0;i<n;i++){
cin>>u>>k;
for(int j=0;j<k;j++){
cin>>v>>c;
mp[u].push_back(make_pair(v,c));
}
}
printf("%d\n", dijkstra(1,n));
return 0;
}最短路径问题—Dijkstra算法详解 https://blog.csdn.net/qq_35644234/article/details/60870719
dijkstra(链式前向星)
#include <iostream>
#include <algorithm>
#include <cstring>
#include<cstdio>
#include <queue>
#define INF 0x3f3f3f
#define maxn 10010
using namespace std;
struct Time{
int w, e;
bool operator < (const Time& t)const{
return w > t.w;
}
};
struct node{
int w;
int e;
int next;
}edge[maxn];
int cnt,t,n;
int head[maxn];
void init(){
memset(head,0,sizeof head);
cnt=1;
}
void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].e=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int dijkstra(){
priority_queue<Time> q;
int d[maxn];
memset(d,INF,sizeof d);
d[1]=0;
q.push(Time{
0,1});
while(!q.empty()){
Time st=q.top();
q.pop();
if(d[st.e]<st.w) continue;
for(int i=head[st.e];i!=0;i=edge[i].next){
if(d[st.e]+edge[i].w<d[edge[i].e]){
d[edge[i].e]=d[st.e]+edge[i].w;
q.push(Time{
d[edge[i].e],edge[i].e});
}
}
}
return d[n];
}
int main(){
while(~scanf("%d %d", &t, &n)){
init();
int u,v,w;
for(int i=0;i<t;i++){
scanf("%d %d %d", &u, &v, &w);
add(u,v,w);
add(v,u,w);
}
printf("%d\n", dijkstra());
}
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/226940.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022年10月30日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
推荐阅读
相关推荐
ZOJ 3794 Greedy Driver spfa
更多 >
腾讯云开发者
