常见最短路

在图论中，源点—起点 汇点—终点

  • 单源最短路

    • 所有边权都是正数

      • 朴素Dijkstra算法 O(n^2) ==邻接矩阵==

        与m（边）无关 适用于稠密图（用邻接矩阵来存）

      • 堆优化版的Dijkstra算法 O(mlogn)

        适用于稀疏图（用邻接表来存）

    • 存在负权边

      • Bellman-Ford O(nm)
      • SPFA 一般：O(m)，最坏O(nm) ==邻接表== （稀疏图）

  • 多源汇最短路

    • Floyd算法 O(n^3)

Dijkstra()

Dijkstra算法求最短路（第一个点到终点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//朴素的Dijkstra
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];//g[i][j]为i->j的边的权重
int dist[N];//点到起点的最短距离
bool st[N]; 
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);//先将距离初始化为正无穷
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
			if(!st[j] && (t==-1 || dist[t]>dist[j]))
                t=j;
        //if(t==n)	break;		可加上
        
        st[t]=true;
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f)	return -1;
    return dist[n];
}
int main()
{
   cin>>n>>m;
   memset(g,0x3f,sizeof g);//初始化边为无穷大
   while(m--)
   {
       int a, b, c;
       cin>>a>>b>>c;
       g[a][b]=min(g[a][b],c);//有重边，取最小的一条边
   }
   int t=dijkstra();
    
   cout<<t<<endl;
    
   return 0;
}


//朴素版Dijkstra()

用dijkstra算法求==任意两点==的最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//用dijkstra算法求任意两点的最短路
#include <bits/stdc++.h>
using namespace std;
const int N = 550;
int n,m; 
int g[N][N];
int dist[N], w[N];
bool st[N];
int dijkstra(int start,int end)
{
	memset(dist,0x3f3f3f3f,sizeof(dist));
	memset(st, false, sizeof(st));//每一次有每一次的标记点 
	dist[start]=0;
	
	for(int i=0;i<n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		{
			if(!st[j] && (t==-1 || dist[t]>dist[j]))
			{
				t=j;
			}
		}
		st[t]=true; 
		for(int j=1;j<=n;j++)
		{
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}
	
	return dist[end];
}

int main()
{
	while(1)
	{
		cin>>n>>m;
		if(n==0&&m==0)	break;
		//初始化
		memset(g,0x3f3f3f3f,sizeof(g));
		for(int i=1;i<=n;i++)	cin>>w[i];
		while(m--)
		{
			int a,b,c;
			cin>>a>>b>>c;
			if(a==1){
				g[b][c]=abs(w[b]-w[c]);
			}else{
				g[b][c]=g[c][b]=abs(w[b]-w[c]);
			}
		}
		int start,end;
		cin>>start>>end;
		cout<<dijkstra(start,end)<<endl;
	}

	
	return  0;
 }

Bellman_Ford()

Bellman_Ford算法求最短路（对通过的边数有要求就用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 100010;
int n, m, k;//k是限制的边数
int dist[N], backcup[N];
struct Edge
{
    int a, b, w;
}edges[M];
int bellman_ford()
{
    memset(dist,0x3f,sizeof(dist));	//初始化
    dist[1]=0;
    
    for(int i=0;i<k;i++)
    {
        memcpy(backcup,dist,sizeof(dist));
        for(int j=0;j<m;j++)//**m是要存储的边的数量，而这里恰好是m条
        {
            int a=edges[j].a, b=edges[j].b, w=edges[j].w;
            dist[b]=min(dist[b], backcup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2)	return -1;//(注意这里如果最短距离是-1，而返回值有是-1就错了，所以要看清题注意特征值)
    return dist[n];
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }
    
    int t=bellman_ford();
    if(t==-1)	cout<<"impossible"<<endl;
    else	cout<<t<<endl;
    
    return 0;
}

-----------------------------------------------分割线---------------------------------------------------
    
//一道及其恶心的题(要注意bellman_ford返回的值可能就是最短路所以要找到一个特征值)
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 100010;
int n, m, cnt;//*****cnt计数 
int dist[N], backcup[N], dot[N];
struct Edge
{
    int a, b, w;
}edges[M];
long long bellman_ford(int start,int end)
{
    memset(dist,0x3f3f3f3f,sizeof(dist));	//初始化
    dist[start]=0;
    
    for(int i=0;i<1200;i++)
    {
        memcpy(backcup,dist,sizeof(dist));
        for(int j=0;j<cnt;j++)//*****'<cnt'
        {
            int a=edges[j].a, b=edges[j].b, w=edges[j].w;
            dist[b]=min(dist[b], backcup[a]+w);
        }
    }
//    if(dist[end]<50000)	return dist[end]; 
//    else	return -1;
//	-----始终过不了-----(反其道而行之) 如上 
    
    if(dist[end]>0x3f3f3f3f/2)	return 9999;	//没有最短距离
    return dist[end];
}
int main()
{   
    while(1)
	{
		cin>>n>>m;
		//初始化 
		cnt=0;
		if(n==0&&m==0)	break;
		
		for(int i=1;i<=n;i++)	cin>>dot[i];
		for(int i=0;i<m;i++)
		{
			int a,b,c;
			cin>>a>>b>>c;
			int tmp=dot[c]-dot[b];
			if(a==1){
				edges[cnt++]={b,c,tmp};
			}		
			else{
				edges[cnt++]={b,c,tmp}, edges[cnt++]={c,b,tmp*-1};
			}	
		}
		int start, end;
		cin>>start>>end;
		int t=bellman_ford(start,end);
		
		if(t==9999)	cout<<"INF"<<endl;
		else	cout<<t<<endl;
		
	}
    
    return 0;
}

Spfa()

用Spfa算法求解带负权边的问题（全正的大部分也能做）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
int st[N];
void add(int a,int b,int c)
{
    e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}
int spfa()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    
    queue<int> q;
    q.push(1);
    st[1]=true;
    
    while(q.size())
    {
        int t=q.front();
        q.pop();	//移除队首元素
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    
    if(dist[n]==0x3f3f3f3f)		return -1;
    return	dist[n]; 
    
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--)
    {
        int a, b ,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    
	int t=spfa();
    if(t==-1)	cout<<"impossible"<<endl;
    else	cout<<t<<endl;

    return 0;
}

用spfa判断有无负权环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N], cnt[N];
int st[N];
void add(int a,int b,int c)
{
    e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}
bool spfa()
{  
    queue<int> q;
    
    for(int i=1;i<=n;i++)
	{
		st[i]=true;
		q.push(i);	
	} 
    
    while(q.size())
    {
        int t=q.front();
        q.pop();	//移除队首元素
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)	return true;
                
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    
    return false;
    
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--)
    {
        int a, b ,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    
	if(spfa())	cout<<"yes"<<endl;//说明有负环 
	else	cout<<"no"<<endl;

    return 0;
}