当前位置: 代码迷 >> 综合 >> 图论——最短路算法学习笔记
  详细解决方案

图论——最短路算法学习笔记

热度:30   发布时间:2024-01-18 18:49:41.0

最短路算法
1.FLOYD算法
多源最短路
预处理:
二维数组储存两点之间的边距离,初始化为正无穷即可。自己到自己为0;
核心代码:
int inf = 999999;
for(int k=1;k<=n;k++) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(e[i][k]<inf&&e[k][j]<inf&&e[i][j]>e[i][k]+e[k][j]) {
                e[i][j]=e[i][k]+e[k][j];
            }
        }
    }
}
弊端:可以处理负权图,但是不能处理负权环;

 

2.Dijkstra
单源最短路
预处理:二维数组储存两点之间距离同上。额外需要一位数组储存某一点到其余各点初始路程。
基本思想:寻找离源点最近的一个顶点,然后以该点为中心点扩展。
基本步骤:1,分组,首先将所有点分为两部分,已知最短路程的和未知的。(可以使用一个一维bool数组book表示)
2.设置源点自身距离为0,如果有可直接到达源点的点dis[i]即置为e[s][i],同时将其余点置为inf。
3.找到一个dis最小的点加入P ,并且进行每一条边的松弛操作扩展路径。
4.重复直到P中没有元素。

核心代码:
//初始化dis book
for(int i=1;i<=n;i++)  dis[i]=e[1][i];

for(int i=1;i<=n;i++) book[i] = 0;
book [1]=1;

//DIJKSTRA
for(int i=1;i<=n;i++) {
    min=inf;
    for(int j=1;j<=n;j++) {
        if(book[j]==0&&dis[j]<min) {
            min=dis[j];                
            u=j;                    //找到距离1号点最短的点
        }
    }
    book[u]=1;
    for(int v=1;v<=n;v++) {
        if(e[u][v]<inf) {            //依次松弛
            if(dis[v]>dis[u]+e[u][v]) 
                dis[v]=dis[u]+e[u][v];
        }
    }
}

 


*数组实现临接表
int n,m,i;
int u[6],v[6],w[6]; //需根据实际情况,要比m的最大值大1
int first[5],next[6];//first要比n大1,next要比m大1

cin>>n>>m;

for(int i=1;i<=n;i++) first[i]=-1;
//核心
for(int i=1;i<=m;i++) {
    cin>>u[i]>>v[i]>>w[i];
    next[i]=first[u[i]];
    first[u[i]]=1;
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1001;
const int M = 10001;struct edge {int v, w, next;edge(){}edge(int _v, int _w, int _next) {v = _v;w = _w;next = _next;}
} e[M * 2];int head[N], size;void init() {memset(head, -1, sizeof(head));size = 0;
}void insert(int u, int v, int w) {e[size] = edge(v, w, head[u]);head[u] = size++;
}void insert2(int u, int v, int w) {insert(u, v, w);insert(v, u, w);
}int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {memset(vis,false,sizeof(vis));memset(dis,0x3f,sizeof(dis));dis[u]=0;for(int i=0;i<n;i++) {int mind=1000000000,minj=-1;for(int j=1;j<=n;++j) {if(!vis[j]&&dis[j]<mind) {minj=j;mind=dis[j];}}if(minj==-1) {return;}vis[minj]=true;for(int j=head[minj];~j;j=e[j].next) {int v=e[j].v;int w=e[j].w;if(!vis[v]&&dis[v]>dis[minj]+w) {dis[v]=dis[minj]+w;}}}
}
int main() {init();int u,v,w;cin>>n>>m;while(m--) {cin>>u>>v>>w;insert2(u,v,w);}dijkstra(1);cout<<dis[n]<<endl;return 0;
}


3.Bellman-Ford
重要思想:对n个顶点的图只需遍历松弛n-1次即可得到最短路,同时,最短路径一定不包括环。
初始未优化代码:

//初始化dis
for(int i=1;i<=n;i++) dis[i]=inf;
dis[1]=0;

//核心 n为顶点个数,m为边条数 w储存权值
for(int k=1;k<=n-1;k++) {
    for(int i=1;i<=m;i++) {
        if(dis[v[i]]> dis[u[i]] + w[i]) 
            dis[v[i]] = dis[u[i]] + w[i]; 
    }
}

//检测负环
flag=0;
if(dis[v[i]]> dis[u[i]] + w[i]) flag=1;
if(flag) cout<<"存在负权回路";
 

  相关解决方案