Dijkstra
模板一（map数组模拟邻接表）
处理小图速度相对较快。
内存占用较小，对重边优化较差。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000;
int map[maxn][maxn];
int pre[maxn],dis[maxn];
bool vis[maxn];
int n,m;
void Dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;++i)
{
dis[i]=map[s][i];
pre[i]=s;
}
dis[s]=0;
vis[s]=true;
for(int i=2;i<=n;++i)
{
int mindist=INF;
int u=s;
for(int j=1;j<=n;++j)
if((!vis[j])&&dis[j]<mindist)
{
u=j;
mindist=dis[j];
}
vis[u]=true;
for(int j=1;j<=n;++j)
if((!vis[j])&&map[u][j]<INF)
{
if(map[u][j]+dis[u]<dis[j])
{
dis[j]=map[u][j]+dis[u];
pre[j]=u;
}
}
}
}
int main(){
cin >> m >> n;
for (int i=1; i <=n;i++)
for (int j=1;j <=n;j++){
if (i == j) map[i][j] = 0;
else map[i][j] = map[j][i] = INF;
}
while (m--) {
int start, end, len;
cin >> start >> end >> len;
map[start][end] = len;
map[end][start] = len;
}
cout << map[2][5] << endl;
Dijkstra(1);
cout << dis[n] << endl;
return 0;
}
模板二（链式前向星+优先队列优化）
主要优化在重边。因为使用了STL所以占用内存和速度相对较慢。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
struct node
{
int d,u;
friend bool operator<(node a,node b)
{
return a.d>b.d;
}
node(int dist,int point):d(dist),u(point){}
};
struct Edge
{
int to,next;
int dist;
}edge[maxm];
int head[maxn],tot;
int pre[maxn],dis[maxn];
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void addedge(int u,int v,int d)
{
edge[tot].to=v;
edge[tot].dist=d;
edge[tot].next=head[u];
head[u]=tot++;
}
void Dijkstra(int s)
{
priority_queue<node> q;
memset(dis,0x3f,sizeof(dis));
memset(pre,-1,sizeof(pre));
dis[s]=0;
while(!q.empty())
q.pop();
node a(0,s);
q.push(a); //起点入队列
while(!q.empty())
{
node x=q.top();
q.pop();
if(dis[x.u]<x.d) //最短路已找到
continue;
for(int i=head[x.u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[x.u]+edge[i].dist)
{
dis[v]=dis[x.u]+edge[i].dist;
pre[v]=x.u;
q.push(node(dis[v],v));
}
}
}
}
模板三（结构体内置方法）
因为使用了链式前向星所以不担心重边。
其中还使用了快读方法，所以很快。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
const int N = 1005;
const int M = 1005;
const int INF = 0x3f3f3f3f
struct Graph{
struct Edge{
int v, w, next;
}edge[M];
int ehead[N];
void init(){
memset(ehead, -1, sizeof(ehead))
}
inline void addedge(int u, int v, int w){
edge[ecnt] = {v, w, ehead[u]};
ehead[u] = ecnt++;
}
int dist[N];
bool vis[N];
void Dijkstra(int s){
memset(dist, INF, sizeof(dist));
memset(vis, 0, sizeof(vis));
priority_queue<pair<int, int> > q;
q.push(make_pair(-(dist[s] = 0), s));
while(q.size()){
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = ehead[u]; ~i; i = edge[i].next){
int v = edge[i].v;
if (vis[v]) continue;
int ndist = dist[u] + edge[i].w;
if (ndist < dist[v]) q.push(make_pair(-(dist[v] = ndist), v));
}
}
}
}g1, g2;
int Input(){
char c;
for (c = getchar(); c<'0' || c>'9'; c = getchar());
int a = c - '0';
for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
a = a*10 + c - '0';
return a;
}
Floyd
代码很短，时间复杂度很高（O(n^3)）。
void floyd(){
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if (map[i][j] > map[i][k] + map[k][j]) //松弛
map[i][j] = map[i][k] + map[k][j];
}
Bellman-Ford
模板一（链式前向星）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
struct Edge{
int u, v;
double r, c;
}edge[maxn*2];
double mostMoney[maxn];
int n, m, s;
double v;
int tot;
void addedge(int u, int v, double r, double c){
edge[tot].u = u;
edge[tot].v = v;
edge[tot].r = r;
edge[tot++].c = c;
}
bool relax(int n){
double temp = (mostMoney[edge[n].u] - edge[n].c)*edge[n].r;
if (temp > mostMoney[edge[n].v]){
mostMoney[edge[n].v] = temp;
return true;
}
return false;
}
bool bellman_ford(){
bool flag;
for (int i=0; i<n; i++) mostMoney[i] = 0.0;
mostMoney[s] = v;
for (int i=0; i<n-1; ++i){
flag = false;
for (int j=0; j<tot; ++j)
if (relax(j)) flag = true;
if (mostMoney[s] > v) return true;
if (!flag) return false;
}
for (int i=0; i<tot; ++i){
if (relax(i)) return true;
}
return false;
}
模板二
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
struct Edge{
int u,v; //起点、终点
int dist; //长度
}edge[maxn];
int dis[maxn]; //最短距离数组
int n, m; //结点数、边数
bool Bellman_ford(int s){
memset(dis, INF, sizeof(dis));
dis[s]=0;
for(int k=1; k<n; ++k){ //迭代n-1次
for(int i=0; i<m; ++i){ //检查每条边
int x = edge[i].u, y = edge[i].v;
if(dis[x] < INF)
dis[y] = min(dis[y], dis[x] + edge[i].dist);
}
}
bool flag=1;
for(int i=0; i<m; ++i){ //判断是否有负环
int x = edge[i].u, y = edge[i].v;
if(d[y] > d[x] + edge[i].dist){
flag = 0; break;
}
}
return flag;
}
SPFA
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1000005
using namespace std;
const long long INF = 0xffffffff;
int Input(){
char c;
for (c = getchar(); c<'0' || c>'9'; c = getchar());
int a = c - '0';
for (c = getchar(); c>='0' && c<='9'; c = getchar()) a = a * 10 + c - '0';
return a;
}
int n, m;
struct edge{
int e, next, w;
}edge[2][maxn];
long long dis[maxn], ans;
int head[2][maxn], vis[maxn];
inline void spfa(int x){
for (int i=1; i<=n; i++){
dis[i] = 0xffffffff;
//cout << dis[i] << endl;
}
memset(vis, 0, sizeof(vis));
queue<int> q;
int a, b;
q.push(1);
vis[1] = 1;
dis[1] = 0;
while(!q.empty()){
a = q.front(); q.pop();
vis[a] = 1;
for (int i=head[x][a]; i != -1; i=edge[x][i].next){
b = edge[x][i].e;
if (dis[b] > dis[a] + edge[x][i].w){
dis[b] = dis[a] + edge[x][i].w;
if (!vis[b]) { q.push(b); vis[b] = 1; }
}
}
}
}
网友评论