文章目录
邻接表存储 - 无权图的单源最短路算法（C++描述）Dijkstra算法：单源最短路（未使用堆优化）Dijkstra算法：单源最短路（使用堆优化）Floyd算法：多源最短路SPFA算法：可以求负权图
邻接表存储 - 无权图的单源最短路算法（C++描述）
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
vector
<int> g
[100];
queue
<int> qu
;
int dist
[100];
int path
[100];
int main(){
int n
;
cin
>>n
;
memset(path
,-1,sizeof(path
));
while(n
--){
int u
,v
;
cin
>>u
>>v
;
g
[u
].push_back(v
);
}
int m
;
bfs(m
);
}
void bfs(int start
){
qu
.push(start
);
while(!qu
.empty()){
int now
=qu
.front();
qu
.pop();
for(auto nxt
:g
[now
]){
if(dist
[nxt
]==-1){
dist
[nxt
]=dist
[now
]+1;
path
[nxt
]=now
;
qu
.push(nxt
);
}
}
}
}
Dijkstra算法：单源最短路（未使用堆优化）
#include<bits/stdc++.h>
using namespace std
;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll
;
struct Edge
{
int z
,val
,nexty
;
}edge
[200005];
int head
[20000];
int cnt
=0;
void add(int a
,int b
,int c
){
cnt
++;
edge
[cnt
].z
=b
;
edge
[cnt
].val
=c
;
edge
[cnt
].nexty
=head
[a
];
head
[a
]=cnt
;
}
int main(){
bool vis
[20000]={0};
ll dis
[20000];
int n
,m
,s
;
int a
,b
,c
;
cin
>>n
>>m
>>s
;
for(int i
=1;i
<=n
;i
++){
dis
[i
]=0x7fffffff;
}
for(int i
=0;i
<m
;i
++){
cin
>>a
>>b
>>c
;
add(a
,b
,c
);
}
int now
=s
;
dis
[s
]=0;
ll minn
=0x7fffffff;
while(!vis
[now
]){
vis
[now
]=1;
for(int i
=head
[now
];i
;i
=edge
[i
].nexty
){
if(!vis
[edge
[i
].z
]&&dis
[edge
[i
].z
]>dis
[now
]+edge
[i
].val
){
dis
[edge
[i
].z
]=dis
[now
]+edge
[i
].val
;
}
}
minn
=0x7fffffff;
for(int i
=1;i
<=n
;i
++){
if(!vis
[i
]&&minn
>dis
[i
]){
minn
=dis
[i
];
now
=i
;
}
}
}
for(int i
=1;i
<=n
;i
++) cout
<<dis
[i
]<<" ";
}
Dijkstra算法：单源最短路（使用堆优化）
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
struct Edge
{
int z
,val
,nexty
;
}edge
[1000000];
int head
[200000];
ll dis
[200000];
bool vis
[200000]={0};
int cnt
=0;
inline void add(int a
,int b
,int c
){
cnt
++;
edge
[cnt
].z
=b
;
edge
[cnt
].val
=c
;
edge
[cnt
].nexty
=head
[a
];
head
[a
]=cnt
;
}
struct node
{
int dis
;
int pos
;
bool operator<(const node
&x
)const{
return x
.dis
<dis
;
}
};
priority_queue
<node
> q
;
int main(){
int n
,m
,s
;
int a
,b
,c
;
scanf("%d%d%d",&n
,&m
,&s
);
for(int i
=1;i
<=n
;i
++){
dis
[i
]=0x7fffffff;
}
for(int i
=0;i
<m
;i
++){
scanf("%d%d%d",&a
,&b
,&c
);
add(a
,b
,c
);
}
dis
[s
]=0;
q
.push((node
){0,s
});
while(!q
.empty()){
node tmp
=q
.top();
q
.pop();
int x
=tmp
.pos
,d
=tmp
.dis
;
if(vis
[x
]) continue;
vis
[x
]=1;
for(int i
=head
[x
];i
;i
=edge
[i
].nexty
){
int y
=edge
[i
].z
;
if(dis
[y
]>dis
[x
]+edge
[i
].val
){
dis
[y
]=dis
[x
]+edge
[i
].val
;
if(!vis
[y
]){
q
.push((node
){dis
[y
],y
});
}
}
}
}
for(int i
=1;i
<=n
;i
++) printf("%d ",dis
[i
]);
}
Floyd算法：多源最短路
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
using namespace std
;
int dis
[105][105];
typedef long long ll
;
signed main(){
ios
::sync_with_stdio(0);
cin
.tie(0);cout
.tie(0);
int n
,m
,k
;
cin
>>n
>>m
>>k
;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++){
dis
[i
][j
]=0x7fffffff;
}
}
for(int i
=0;i
<m
;i
++){
int a
,b
,c
;
cin
>>a
>>b
>>c
;
dis
[a
][b
]=min(dis
[a
][b
],c
);
}
for(int k
=1;k
<=n
;k
++){
for(int i
=1;i
<=n
;i
++){
if(i
==k
||dis
[i
][k
]==0x7fffffff) continue;
for(int j
=1;j
<=n
;j
++){
if(dis
[i
][k
]+dis
[k
][j
]<dis
[i
][j
]){
dis
[i
][j
]=dis
[i
][k
]+dis
[k
][j
];
}
}
}
}
while(k
--){
int a
,b
;
cin
>>a
>>b
;
if(dis
[a
][b
]==0||dis
[a
][b
]==0x7fffffff){
cout
<<"Nothing to say!"<<endl
;
}else{
cout
<<dis
[a
][b
]<<endl
;
}
}
return 0;
}
SPFA算法：可以求负权图
用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：
队首x出队遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)<dis[i]，则更新dis[i]如果点i不在队列中，则i入队若队列为空，跳出循环；否则执行1
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll
;
struct Edge
{
int to
,val
,nexty
;
}edge
[200005];
int head
[100005],cnt
;
void addedge(int u
,int v
,int val
){
cnt
++;
edge
[cnt
].to
=v
;
edge
[cnt
].val
=val
;
edge
[cnt
].nexty
=head
[u
];
head
[u
]=cnt
;
}
int n
,m
,s
;
int dis
[100005],vis
[100005];
const int inf
=0x7fffffff;
void spfa();
signed main(){
cin
>>n
>>m
>>s
;
for(int i
=1;i
<=m
;i
++){
int u
,v
,val
;
cin
>>u
>>v
>>val
;
addedge(u
,v
,val
);
}
spfa();
for(int i
=1;i
<=n
;i
++){
if(i
==s
) cout
<<0<<" ";
else cout
<<dis
[i
]<<" ";
}
return 0;
}
void spfa(){
queue
<int> qu
;
for(int i
=1;i
<=n
;i
++){
dis
[i
]=inf
;
vis
[i
]=0;
}
qu
.push(s
);dis
[s
]=0;vis
[s
]=1;
while(!qu
.empty()){
int u
=qu
.front();
qu
.pop();
vis
[u
]=0;
for(int i
=head
[u
];i
;i
=edge
[i
].nexty
){
int v
=edge
[i
].to
;
if(dis
[v
]>dis
[u
]+edge
[i
].val
){
dis
[v
]=dis
[u
]+edge
[i
].val
;
if(vis
[v
]==0){
vis
[v
]=1;
qu
.push(v
);
}
}
}
}
}
