最短路径算法

运用了动态规划思想

#include
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(g[i][j]>g[i][k]+g[k][j])
					g[i][j]=g[i][k]+g[k][j];
			}
		}
	}
}

时间复杂度过高( O 3 O^3 O3)，只使用于n≤100的数据。

时间复杂度：( O 3 O^3 O3)

空间复杂度：( O 2 O^2 O2)

算法特点：解决多源最短路径的问题

局限性：能够处理负边权的图，但是不能处理含负环的图（负环不存在最短路径）

基于贪心思想

基本思想：通过贪心思想找出距离源点最近的顶点，再通过该顶点去作为中转顶点来找到下一个距离源点最近的顶点，如此反复直到所有的顶点到源点的距离都被确定。

用数组 d i s [ i ] dis[i] dis[i]表示从源点到i的距离， v i s [ i ] vis[i] vis[i]表示是否访问过i节点。

dis[i]=a[1][i];
dis[1]=0;
vis[1]=1;

if(dis[G]>dis[F]+a[F][G])
    dis[G]=dis[F]+a[F][G];

#include
using namespace std;

int n,m;
int a[105][105];
int dis[10005];
int vis[105];
int s1,t;

int main(){
	memset(a,0x3f,sizeof(a));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=z;
		a[y][x]=z;
	}
	cin>>s1>>t;
	for(int i=1;i 
可以使用堆优化，即用priority_queue储存，依次选取离源点的最小值进行操作
 
见：Dijkstra堆优化 - CaptainLi - 博客园 (cnblogs.com)
 
 
beel-man ford 
#include
using namespace std;
#define inf 100000000

struct edge{
	int x,y,z;
}edge[101];

int n,e,dis[101];

int main(){
	cin>>n>>e;
	for(int i=1;i<=e;i++)	cin>>edge[i].x>>edge[i].y>>edge[i].z;
	for(int i=1;i<=n;i++)	dis[i]=inf;
	dis[1]=0;
	for(int i=1;i<=n-1;i++){
		bool done=0;
		for(int j=1;j<=e;j++){
			if(dis[edge[i].y]>dis[edge[i].x]+edge[i].z){
				dis[edge[i].y]=dis[edge[i].x]+edge[i].z;
				done=1;
			}
		}
		if(done==0)	break;
	}
}
 
 
SPFA 
SPFA算法是Beelman-Ford算法的队列优化算法，通常用于求解含负边权的单源最短路径，以及判断负环。在最坏情况下，SPFA算法的时间复杂度和空间复杂度和Bellman-Ford算法相同，为
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        m
       
       
        )
       
      
      
       O(nm)
      
     
    O(nm)，但在稀疏图上运行效率较高。
 
思路： 
数据结构。链式前向星存储图，
     
      
       
        
         d
        
        
         i
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        dis[i]
       
      
     dis[i]记录从源点到节点i的最短路径长度，
     
      
       
        
         v
        
        
         i
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        vis[i]
       
      
     vis[i]标记节点i是否在队列中，
     
      
       
        
         s
        
        
         u
        
        
         n
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        sun[i]
       
      
     sun[i]记录节点i的入队次数。
创建一个队列，源点u入队，标记u在队列中，u的入队次数加1.
松弛操作。取出队头x，标记x不在队列中。考察x的所有出边
     
      
       
        
         i
        
        
         (
        
        
         x
        
        
         ,
        
        
         v
        
        
         ,
        
        
         w
        
        
         )
        
       
       
        i(x,v,w)
       
      
     i(x,v,w)，如果
     
      
       
        
         d
        
        
         i
        
        
         s
        
        
         [
        
        
         v
        
        
         ]
        
        
         >
        
        
         d
        
        
         i
        
        
         s
        
        
         [
        
        
         x
        
        
         ]
        
        
         +
        
        
         e
        
        
         [
        
        
         i
        
        
         ]
        
        
         .
        
        
         w
        
       
       
        dis[v]>dis[x]+e[i].w
       
      
     dis[v]>dis[x]+e[i].w，则
     
      
       
        
         d
        
        
         i
        
        
         s
        
        
         [
        
        
         i
        
        
         ]
        
        
         =
        
        
         d
        
        
         i
        
        
         s
        
        
         [
        
        
         x
        
        
         ]
        
        
         +
        
        
         e
        
        
         [
        
        
         i
        
        
         ]
        
        
         .
        
        
         w
        
       
       
        dis[i]=dis[x]+e[i].w
       
      
     dis[i]=dis[x]+e[i].w。如果节点v不在队列中，如果v的入队次数+1后≥n，则说明有负环，退出；否则v入队，标记v在队列中。
重复松弛操作，直至队列为空。
 
链式前向星存储： 
int cnt=0;

struct edge{
	int to;
	int dis;
	int next;
}edge[105];

void addedge(int from,int to,int dis){
	edge[++cnt].next=head[from];
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	head[from]=cnt;
}

 
代码： 
#include
using namespace std;

int cnt=0;
int vis[105];
int dis[105];
int sum[105];
int head[105];
int n;

struct edge{
	int to;
	int dis;
	int next;
}edge[105];

void addedge(int from,int to,int dis){
	edge[++cnt].next=head[from];
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	head[from]=cnt;
}

bool spfa(int u){
	queueq;
	memset(vis,0,sizeof(vis));
	memset(sum,0,sizeof(sum));
	memset(dis,0x3f,sizeof(dis));
	dis[u]=0;
	vis[u]=1;
	sum[u]++;
	q.push(u);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=edge[i].next){
			int v=edge[i].to;
			if(dis[v]>dis[x]+edge[i].dis){
				dis[v]=dis[x]+edge[i].dis;
				if(!vis[v]){
					if(++sum[v]>=n)	return true;//负环退出
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return false;
}

int main(){
	cin>>n;
	int u,t;
	cin>>u>>t;
	if(!spfa(u))	cout< 
 
 
时间复杂度：最坏情况下是
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         m
        
        
         )
        
       
       
        O(nm)
       
      
     O(nm)，对于稀疏图时间复杂度为
     
      
       
        
         O
        
        
         (
        
        
         k
        
        
         m
        
        
         )
        
       
       
        O(km)
       
      
     O(km)，k为一个较小常数
 
 
空间复杂度：包含数组edge[]，dist[]，空间复杂度为
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         +
        
        
         m
        
        
         )
        
       
       
        O(n+m)
       
      
     O(n+m)
 
 
优势：可以判断负环
 
 
算法优化 
SLF优化 
SLF策略(small label first)：如果待入队节点是j，队首元素为节点i，若
    
     
      
       
        d
       
       
        i
       
       
        s
       
       
        [
       
       
        j
       
       
        ]
       
       
        <
       
       
        d
       
       
        i
       
       
        s
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       dis[j] 
LLL优化 
LLL策略(large label last)：设队首元素为节点i，队列中所有dis[]的平均值为x，若
    
     
      
       
        d
       
       
        i
       
       
        s
       
       
        [
       
       
        i
       
       
        ]
       
       
        >
       
       
        x
       
      
      
       dis[i]>x
      
     
    dis[i]>x，则将节点插入队尾，查找下一元素，直到某一节点i满足
    
     
      
       
        d
       
       
        i
       
       
        s
       
       
        [
       
       
        i
       
       
        ]
       
       
        ≤
       
       
        x
       
      
      
       dis[i]≤x
      
     
    dis[i]≤x，将节点i出队，进行松弛操作。
 
 
 
SLF和LLL在随机数据上表现优秀，但是在正权图上最坏情况为
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         m
        
        
         )
        
       
       
        O(nm)
       
      
     O(nm)，在负权图上的最坏情况为达到指数级复杂度。
 
 
 
 
最短路径算法比较：几大最短路径算法比较_shiwei408的博客-CSDN博客