spfa(链式前向星)+dijkstra(链式前向星)

spfa(链式前向星)+dijkstra(链式前向星)链式前向星链式前向星可以存图,它存图的方式是:将任意一个节点的所有临边按输入顺序依次连接起来将任意一个节点的所有临边按输入顺序依次连接起来将任意一个节点的所有临边按输入顺序依次连接起来然后头节点(数组)存的是最后一个临边的地址然后头节点(数组)存的是最后一个临边的地址然后头节点(数组)存的是最后一个临边的地址inthead[maxn];//head[i]中i是u->v中的u,he…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

链式前向星

链式前向星可以存图
它存图的方式是:
将 任 意 一 个 节 点 的 所 有 临 边 按 输 入 顺 序 依 次 连 接 起 来 将任意一个节点的所有临边按输入顺序依次连接起来
然 后 头 节 点 ( 数 组 ) 存 的 是 最 后 一 个 临 边 的 地 址 然后头节点(数组)存的是最后一个临边的地址 ()

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];

Jetbrains全家桶1年46,售后保障稳定

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 spfabfs

#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+贪心 dijkstraBFS+

#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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/226940.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ??牛客网–点菜问题(01背包问题)

    ??牛客网–点菜问题(01背包问题)

  • r软件的下载与安装_R语言怎么安装

    r软件的下载与安装_R语言怎么安装一、R软件下载下载地址:https://cran.r-project.org/图1R软件下载页面下载之后是.exe执行文件,不是zip压缩格式文件,可以直接点击安装。二、R软件安装过程一直向下执行,直到安装完毕。最后一步是设置系统环境变量:三、Rstudio下载及安装过程下载地址:https://www.rstudio.com/products/rstudio/downl…

  • 图像的卷积操作

    图像的卷积操作原理:给定一个奇数尺寸大小的卷积核,对图像进行卷积操作。因为使用奇数尺寸大小的卷积核,其锚点正好在卷积核正中央的位置。如下图中间画了一个锚的就是锚点使锚点覆盖在待计算像素上面,然后计算像素值与被覆盖的卷积核中的值的乘积和。将这个和赋值给当前像素,这就是卷积的过程。公式如下所示此处会有一个问题,如果锚点落在第一个像素点(1,1)上,卷积核当中锚点左侧和上方的卷积值超出了图像的边界外…

  • Android Animation:这一次让你彻底了解 Android Frame Animation「建议收藏」

    Android Animation:这一次让你彻底了解 Android Frame Animation「建议收藏」Android Animation:这一次让你彻底了解 Android Frame Animation

  • rsyslogd 重启_Linux系统rsyslogd服务及启动方法[通俗易懂]

    rsyslogd 重启_Linux系统rsyslogd服务及启动方法[通俗易懂]在CentOS6.x中,日志服务已经由rsyslogd取代了原先的rsyslogd。RedHat公司认为rsyslogd已经不能满足工作中的需求,rsyslogd相比rsyslogd具有一些新的特点:基于TCP网络协议传输日志信息。更安全的网络传输方式。有日志信息的即时分析框架。后台数据库。在配置文件中可以写简单的逻辑判断。与syslog配置文件相兼容。rsyslogd日志服务更加先进,功能更…

  • Java Web安全之代码审计

    Java Web安全之代码审计信息安全的75%发生在Web应用而非网络层。本文内容主要以JavaWeb安全-代码审计为中心展开。一、JavaWeb安全基础1.何为代码审计?通俗的说Java代码审计就是通过审计Java代码来发现Java应用程序自身中存在的安全问题,由于Java本身是编译型语言,所以即便只有class文件的情况下我们依然可以对Java代码进行审计。对于未编译的Java源代码文件我们可以直接阅读其…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号