最短路总结

第一种:floyd_warshall

　　简单点说就是三重FOR循环

　　从一点到另一点寻找他们中间能否一有点作为媒介使得他们的权值(距离)更小

　　如果有就更新他们的距离(权值);

　　而中间媒介点靠的就是最外层的FOR循环

　　附上源码:

#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x3f3f3f3f
#define mnum 1000
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,map[mnum][mnum];
floyd_warshall()//弗洛伊德 
{
    for(int k=1; k<=n; k++)//中间边(媒介)遍历
        for(int i=1; i<=n; i++)//
            for(int j=1; j<=n; j++)
                if(map[i][k]!=inf&&map[k][j]!=inf
                        &&map[i][j]>map[i][k]+map[k][j])
                    map[i][j]=map[i][k]+map[k][j]
                }
int main()
{
    int first,last;
    while(cin>>n>>m>>fist>>last)
    {
        mm(map,inf);
        for(int i=1; i<=n; i++)
            map[i][i]=0;
        while(m--)
        {
            int u,v,w;
            cin>>u>>v>>map[u][v];
        }
        floyd_warshall()
        cout<<map[first][last]<<endl;
    }
    return 0;
}

第二种:dijkstra

其时和弗洛伊德算法差不多都是找媒介点更新距离(权值)

只不过他有一个查找距离起始点最近的然后更新对应的(松弛)

而且比弗洛伊德的优势是他能够便捷的求出终点到各点的值

对于来回问题比较容易求解

附上源码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxx 1005
#define inf 0x3f3f3f3f//自定义最大值 
#define mem(a,b) memset(a,b,sizeof(a))
//重新定义 初始化函数  
using namespace std;
int n,m,fid,dis[maxx],vis[maxx],map[maxx][maxx],total[maxx];
void dijkstra(int fir)
{
    mem(dis,0x3f);
    mem(vis,0);
    dis[fir]=0;
    for(int i=1; i<=n; i++)
    {
        int minn=inf,k;
        for(int j=1; j<=n; j++)//寻找距离源/次源点最近的点
            if(!vis[j]&&dis[j]<minn)
            {
                k=j;
                minn=dis[j];
            }
        vis[k]=1;
        for(int j=1; j<=n; j++)
        {
            if(dis[j]>minn+map[k][j])//源点到各点(松弛)
                dis[j]=minn+map[k][j];
        }
    }
}
void dijkstraa(int fir)
{
    mem(dis,0x3f);
    mem(vis,0);
    dis[fir]=0;
    for(int i=1; i<=n; i++)
    {
        int minn=inf,k;
        for(int j=1; j<=n; j++)//寻找到源/次源点最近
            if(!vis[j]&&dis[j]<minn)
            {
                k=j;
                minn=dis[j];
            }
        vis[k]=1;
        for(int j=1; j<=n; j++)
        {
            if(dis[j]>minn+map[j][k])//各点到源点(松弛)
                dis[j]=minn+map[j][k];
        }
    }
}
int main()
{
    cin>>n>>m>>fid;
    mem(map,0x3f);//快速赋值(字节赋值) 
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        map[a][b]=c;
    }
    dijkstra(fid);//传递源点
    for(int i=1; i<=n; i++)
        total[i]=dis[i];
    dijkstraa(fid);//传递源点
    int minn=0;
    for(int i=1; i<=n; i++)
    {
        int c=total[i]+dis[i];
        if(c>minn)
            minn=c;
    }
    cout<<minn<<endl;
    return 0;
}

第三种:bellman_ford

其时原理都不尽相同

n-1次遍历不断更新(松弛)

源码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define inf 0x3f3f3f3f
 5 #define nan -inf
 6 #define scale 105//规模 scale 
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 using namespace std;
 9 
10 int n,m,dis[scale];
11 
12 struct node
13 {
14     int u,v,w;
15 } p[scale];
16 
17 void bellman_ford(int origin)
18 {
19     dis[origin]=0;
20     for(int k=1; k<n; k++) //n-1次遍历
21         for(int i=0; i<m; i++)
22         {
23             //这里是双向的要一起判断 否则就凉凉
24             if(dis[p[i].u]>dis[p[i].v]+p[i].w)
25                 dis[p[i].u]=dis[p[i].v]+p[i].w;
26             if(dis[p[i].v]>dis[p[i].u]+p[i].w)
27                 dis[p[i].v]=dis[p[i].u]+p[i].w;
28         }
29 
30 }
31 int main()
32 {
33     int origin,terminus;
34     while(cin>>n>>m>>origin>>terminus)//起点终点
35     {
36         mem(dis,inf);
37         for(int i=0; i<m; i++)
38         {
39             cin>>p[i].u>>p[i].v>>p[i].w;
40         }
41         bellman_ford(origin);
42         cout<<dis[terminus]<<endl;
43     }
44     return 0;
45 }

关于dijkstra的优化,SPFA后期会加上