目录

前言

单源路最短路径

       朴素版的Dijkstra算法：

       堆优化版的的Dijkstra算法：

       bellman-ford算法：

       SPAF算法：

 多元最短路：

        Floyd算法：

 总结

      

         

---

前言：

   通过本章节的学习，能使你对图论中的最短路径有一定的认识。再通过一定的刷题联系，能够掌握基本的图论最短路径问题。

     最短路问题分为：

          1.单源最短路

              1.1：所有边权都为正的最短路问题。

                      解决方案：

                             1.朴素版的Dijkstra算法。

                             2.堆优化版的Dijkstra算法。

             1.2：存在负边权的最短路问题。

                     解决方案：

                              1.bellman-ford算法。

                              2.SPFA算法。

          2.多元最短路

                     解决方案：

                               Floyd算法。

单源路最短路径：

   朴素版的Dijkstra算法：

                迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

                 扩展的过程：找到始点距离最近且未访问过的顶点，用这个点去“松弛”其他的点。接下来我们用一道实例来看。

例题：

         拿样例来模拟松弛的过程。

       dis数组是1号点到其他点走k步的最短距离

               

 题解：

#include 
#include 
#include  
using namespace std;
const int N=510;
int map[N][N],dis[N],m,n;
bool book[N];//用于标记，将松弛过的点标记一下。以后不再松弛这个点
int dijkstra()
{
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;//自己到自己 
	for(int i=1;i<=n;i++)
	{
		int k=-1;
		for(int j=1;j<=n;j++)
		if(!book[j]&&(k==-1||dis[k]>dis[j]))
		k=j;
		book[k]=true;
		for(int j=1;j<=n;j++)
		dis[j]=min(dis[j],map[k][j]+dis[k]);
	}
	if(dis[n]==0x3f3f3f3f) return -1;
	else return dis[n];
}
int main()
{
	//先对邻接矩阵进行初始化
	memset(map,0x3f,sizeof map); 
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		map[a][b]=min(c,map[a][b]);
	}
	cout< 
 堆优化版的的Dijkstra算法： 
          
 
    其过程和朴素版的差不多，就是使用了一个堆，进行了优化，在实际写题中用到的不多。大多数都能用SPAF算法代替
 
  代码：
 
#include
#include
#include
#include

using namespace std;

typedef pair PII;
const int N=1000010;
int h[N],ne[N],e[N],w[N],dist[N],idx;//w表示权重
int n,m;
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra()
{
    memset(dist,0x3f,sizeof(dist));
    priority_queue,greater> heap;
    //小根堆的定义方式,PII的第一个变量存储的是距离,第二个变量存储的是该点的编号,内部按照第一个变量排序,即按距离排序
    dist[1]=0;
    heap.push({0,1});
    while(heap.size())
    {
        auto t=heap.top();//选择最小的距离的点
        heap.pop();//利用完该点之后要弹出
        int ver=t.second;//表示该点的编号
        if(st[ver]) continue;
        
        st[ver]=true;//标记该点已经使用过了
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[ver]+w[i])//如果j到起点的距离大于ver到1的距离加上ver到j的距离，就更新值的大小；
            {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
                
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout< 
 bellman-ford算法： 
               贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和莱斯特·福特创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为Edward F. Moore也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。
 
       这个算法可以求出走n步到达某个点的最短路径。（算法有两个循环构成）其外部循环有一个含义，就是循环几次，相当于走了几步。内部循环相当于是对走第n步的松弛。因为在执行这个算法的时候，我们只需要考虑边之间的关系即可，所以直接用一个结构体储存其边之间的关系即可。
 
               
 
这一题看起来和上面一题差不多，但是由于边权有负值，所以不能用Dijkstra算法来解决。
 
为什么不能用dijkstra算法？
 
dijkstra是基于贪心策略,每次都找一个距源点最近的点,然后将该距离定为这个点到源点的最短路径;但如果存在负权边,那就有可能先通过并不是距源点最近的一个次优点,再通过这个负权边,使得路径之和更小,这样就出现了错误。
 
题解：
 
#include 
#include 
using namespace std;//bellman - ford
const int N=1e4+10,M=510;
int st[M],back[M];
int m,n,k,number;
struct ff{
	int x,y,z;
}map[N];
int bellman_ford()
{
	memset(st,0x3f,sizeof st);
	st[1]=0;
	for(int i=1;i<=k;i++)//k是几，就相当于走了多少步
	{
		memcpy(back,st,sizeof st);
		for(int j=0;j>m>>n>>k;
	number=n;
	while(n--)
	{
	   // cout<>a>>b>>c;
		map[n]={a,b,c};
	} 
	if(bellman_ford()<0x3f3f3f3f/2)
		cout< 
 SPAF算法： 
        其实SPAF算法就是优化版的bellman-ford算法。我们在学习benllman-ford算法的时候，会发现，在第二个循环中，会对每一个边都进行处理。而实际上，这里面有些边就没有发生过变化所以造成了时间上的浪费。我们这里可以用一个队列对bellman-ford算法进行一个优化，就是每次仅让最短路程发生变化的点（进队列）的相邻边进行“松弛操作”。这样就避免了很多比必要的过程。
 
                          
 
题解： 
 
#include 
#include 
#include 
using namespace std;
//用邻接矩阵进行储存
const int N=1e5+10;
int head[N],ne[N],e[N],w[N],indx=0;//用邻接表进行储存
int m,n,st[N],book[N];
queue q;
void add(int a,int b,int c)
{
	w[indx]=c;e[indx]=b;ne[indx]=head[a];head[a]=indx++;
}
int spfa(int k)
{
	memset(st,0x3f,sizeof st);
	st[k]=0;
	q.push(k);
	book[k]=1;
	while(!q.empty())
	{
		int s=q.front();
		q.pop();
		book[s]=0;
		for(int i=head[s];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(st[j]>st[s]+w[i])
			{
				st[j]=st[s]+w[i];
				if(book[j]==0)
				{
					q.push(j);
					book[j]=1;
				}
			}
		}
	}
	return st[n];
}
int main()
{
	cin>>n>>m;
	memset(ne,-1,sizeof ne);
	memset(head,-1,sizeof head);
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	if(spfa(1)<0x3f3f3f3f)
	cout< 
 多元最短路： 
        Floyd算法： 
     又被称作是只有五行的算法。
 
基本思想就是：最开始只允许经过 1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过 1~n 号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从 i号顶点到j号顶点只经过前 k号点的最短路程。其实这是一种“动态规划”的思想。
 例题：
 
                
 
 题解：
 
#include 
#include 
#include 
using namespace std;
const int N=210;
int a[N][N];
int n,m,k;
int main()
{
	cin>>n>>m>>k;
	memset(a,0x3f,sizeof a);
	for(int i=1;i<=n;i++)
	a[i][i]=0;
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=min(a[x][y],z);//因为可能存在自环 
	}
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
        }
    }//floyd算法的时间复杂度为O（n^2）
	/*	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		cout<>x>>y;
	 	if(a[x][y]>=0x3f3f3f3f/2)
	 	cout<<"impossible"< 
 
 总结： 
        最短路径问题能够解决很多生活中的实际问题，所以掌握这几种常见的算法很重要！
 
 
 
近一周学习的总结！