一：Dijkstra算法（迪科斯彻算法）

迪科斯彻算法用于求解单源最短路径。也就是求解源点和其他各个节点间的最短路径长度。迪科斯彻算法的特点就是利用贪心算法解决单源最短路径问题。他的执行步骤是首先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直至求出从源点到其他各个节点的最短路径。
迪科斯彻的基本思想：假定源点u，节点集合v被划分成两部分：集合S和集合V-S。初始时，在集合S中仅包含源点u，S中的节点到源点的最短路径已确定。集合V-S所包含的源点到节点的长度待定，称从源点出发只经过集合S中的节点到达集合V-S中的节点的路径为特殊路径，并用数组dist[]记录当前每个节点所对应的最短特殊路径长度。
迪科斯彻算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的集合V-S中的节点加入集合S中，同时更新数组dist[]。一旦集合S包含所有节点，dist[]就是从源点到所有其他节点的最短路径长度。

算法步骤：

数据结构的设置：设置地图的邻接矩阵为G.Edge[][]，即如果从源点u到节点i有边，就令G.Edge[u][v]等于的权值，否则G.Edge[u][i]为无穷大；采用一维数组dist[i]记录从源点到节点i的最短路径长度；采用一维数组p[i]记录最短路径上节点i的前驱。
初始化:令集合S={u}，对于集合V-S中的所有节点i，都初始化dist[i]=G.Edge[u][i],如果从源点u到节点i有边相连，则初始化p[i]=u,否则p[i]=-1.
找最小。在集合V-S中查找dist[]最小的节点t，即dist[t] = min(dist[j]|j属于集合V-S)，则节点t就是集合V-S中距离源点u最近的节点。
加入集合S中。将节点t加入集合S中，同时更新集合V-S。
判结束，若集合V-S为空，则算法结束，否则继续下一步骤
已知在步骤三中找到了从源点到节点t的最短路径，那么对集合V-S中节点t的所有邻接点j，都可以借助t走捷径。若dist[j]>dist[t]+G.Edge[t][j],则dist[j]=dist[t]+G.Edge[t][j],记录节点j的前驱为t，有p[j]=t，转向步骤三。

由此可求得从源点u到图G的其余各个节点的最短路径和长度，也可通过数组p[]逆向找到最短路径上的节点。

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int MaxVnum=100; //城市的个数可修改
const int INF=0x3f3f3f3f; //无穷大
int dist[MaxVnum],p[MaxVnum];//最短距离和前驱数组
bool flag[MaxVnum]; //如果s[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S
typedef string VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct{
    VexType Vex[MaxVnum];
    EdgeType Edge[MaxVnum][MaxVnum];
    int vexnum,edgenum; //顶点数，边数
}AMGraph;
int locatevex(AMGraph G,VexType x){
    for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
        if(x==G.Vex[i])
            return i;
    return -1;//没找到
}
void CreateAMGraph(AMGraph &G){
    int i,j,w;
    VexType u,v;
    cout<<"请输入顶点数："<<endl;
    cin>>G.vexnum;
    cout<<"请输入边数:"<<endl;
    cin>>G.edgenum;
    cout<<"请输入顶点信息:"<<endl;
    for(int i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
        cin>>G.Vex[i];
    for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵为无穷大
        for(int j=0;j<G.vexnum;j++)
            G.Edge[i][j]=INF;
    cout<<"请输入每条边依附的两个顶点及权值："<<endl;
    while(G.edgenum--){
        cin>>u>>v>>w;
        i=locatevex(G,u);//查找顶点u的存储下标
        j=locatevex(G,v);//查找顶点v的存储下标
        if(i!=-1&&j!=-1)
            G.Edge[i][j]=w; //有向图邻接矩阵
        else{
            cout<<"输入顶点信息错！请重新输入！"<<endl;
            G.edgenum++;//本次输入不算
        }
    }
}
void Dijkstra(AMGraph G,int u){
    for(int i=0;i<G.vexnum;i++){
        dist[i]=G.Edge[u][i]; //初始化源点u到其他各个顶点的最短路径长度
        flag[i]=false;
        if(dist[i]==INF)
            p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
        else
            p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
    }
    dist[u]=0;
    flag[u]=true;   //初始时，集合S中只有一个元素：源点u
    for(int i=0;i<G.vexnum;i++){
        int temp=INF,t=u;
        for(int j=0;j<G.vexnum;j++) //在集合V-S中寻找距离源点u最近的顶点t
            if(!flag[j]&&dist[j]<temp){
                t=j;
                temp=dist[j];
            }
        if(t==u) return; //找不到t，跳出循环
        flag[t]=true;  //否则，将t加入集合
        for(int j=0;j<G.vexnum;j++)//更新V-S中与t相邻接的顶点到源点u的距离
            if(!flag[j]&&G.Edge[t][j]<INF)
                if(dist[j]>(dist[t]+G.Edge[t][j])){
                    dist[j]=dist[t]+G.Edge[t][j];
                    p[j]=t;
                }
    }
}
void findpath(AMGraph G,VexType u){
    int x;
    stack<int>S;
    cout<<"源点为："<<u<<endl;
    for(int i=0;i<G.vexnum;i++){
        x=p[i];
        if(x==-1&&u!=G.Vex[i]){
            cout<<"源点到其它各顶点最短路径为："<<u<<"--"<<G.Vex[i]<<"    sorry,无路可达"<<endl;
            continue;
        }
        while(x!=-1){
            S.push(x);
            x=p[x];
        }
        cout<<"源点到其它各顶点最短路径为：";
        while(!S.empty()){
            cout<<G.Vex[S.top()]<<"--";
            S.pop();
        }
        cout<<G.Vex[i]<<"    最短距离为："<<dist[i]<<endl;
    }
}
int main(){
    AMGraph G;
    int st;
    VexType u;
    CreateAMGraph(G);
    cout<<"请输入源点的信息:"<<endl;
    cin>>u;
    st=locatevex(G,u);//查找源点u的存储下标
    Dijkstra(G,st);
    cout<<"小明所在的位置:"<<u<<endl;
    for(int i=0;i<G.vexnum;i++){
        cout<<"小明:"<<u<<" - "<<"要去的位置:"<<G.Vex[i];
        if(dist[i]==INF)
            cout<<" sorry,无路可达"<<endl;
        else
            cout<<" 最短距离为:"<<dist[i]<<endl;
    }
    findpath(G,u);
    return 0;
}
/*
5 8
1 2 3 4 5
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
3 5 1
4 3 2
4 5 4
1
*/

时间复杂度和优化。

二：Floyd算法（弗洛伊德算法）

迪科斯彻算法用于求从源点到其他各个节点的最短路径。如果求解任意两个节点之间的最短路径，则需要以每个节点为源点，重复调用n次迪斯科彻算法，其实完全没必要这么麻烦，弗洛伊德算法可用于求解任意两个节点的最短路径。弗洛伊德算法又被称为插点法，其算法核心是在节点i与节点j之间插入节点k，看看是否可以缩短节点i和节点j之间的距离（松弛操作）

算法步骤：

数据结构的设定，设置地图的带权邻接矩阵为G.Edge[][],即如果从节点i到节点j有边，则G.Edge[i][j]=的权值，否则赋值为无穷大；采用两个辅助数组：最短距离数组dist[i][j]，记录从节点i到节点j的最短路径节点j的最短路径长度；前驱数组p[i][j]，记录从节点i到节点j的最短路径上节点j的前驱。
初始化:初始化dist[i][j]=G.Edge[i][j]，如果从节点i到节点j有边相连，则初始化p[i][j]=i,否则p[i][j]=-1.
插点：其实就是在节点i,j之间插入节点k，看看是否可以缩短节点i，j之间的距离（松弛操作），如果dist[i][j]=dist[i][k]+dist[k][i],记录节点j的前驱p[i][j]=p[k][j]。 ```cpp
include
include
using namespace std; const int MaxVnum=100; //顶点数最大值 const int INF=0x3f3f3f3f; // 无穷大 typedef string VexType; //顶点的数据类型，根据需要定义 typedef int EdgeType; //边上权值的数据类型，若不带权值的图，则为0或1 typedef struct{ VexType Vex[MaxVnum]; EdgeType Edge[MaxVnum][MaxVnum]; int vexnum,edgenum; //顶点数，边数 }AMGraph; int dist[MaxVnum][MaxVnum],p[MaxVnum][MaxVnum];

int locatevex(AMGraph G,VexType x){ for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标 if(x==G.Vex[i]) return i; return -1;//没找到 }

void CreateAMGraph(AMGraph &G){//创建无向图的邻接矩阵 int i,j,w; VexType u,v; cout<<”请输入顶点数：”<>G.vexnum; cout<<”请输入边数:”<>G.edgenum; cout<<”请输入顶点信息:”<>G.Vex[i]; for(int i=0;i>u>>v>>w; i=locatevex(G,u);//查找顶点u的存储下标 j=locatevex(G,v);//查找顶点v的存储下标 if(i!=-1&&j!=-1) G.Edge[i][j]=w; //有向图邻接矩阵存储权值 } }

void Floyd(AMGraph G){ //用Floyd算法求有向网G中各对顶点i和j之间的最短路径 int i,j,k; for(i=0;i<G.vexnum;i++) //各对结点之间初始已知路径及距离 for(j=0;j<G.vexnum;j++){ dist[i][j]=G.Edge[i][j]; if(dist[i][j]<INF&&i!=j) p[i][j]=i; //如果i和j之间有弧，则将j的前驱置为i else p[i][j]=-1; //如果i和j之间无弧，则将j的前驱置为-1 } for(k=0;k<G.vexnum;k++) for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) if(dist[i][k]+dist[k][j]<dist[i][j]){//从i经k到j的一条路径更短 dist[i][j]=dist[i][k]+dist[k][j]; //更新dist[i][j] p[i][j]=p[k][j]; //更改j的前驱 } }

void print(AMGraph G){ int i,j; for(i=0;i<G.vexnum;i++){//输出最短距离数组 for(j=0;j<G.vexnum;j++) cout<<dist[i][j]<<”\t”; cout<<endl; } cout<<endl; for(i=0;i<G.vexnum;i++){//输出前驱数组 for(j=0;j<G.vexnum;j++) cout<<p[i][j]<<”\t”; cout<<endl; } }

void DisplayPath(AMGraph G,int s,int t){//显示最短路径 if(p[s][t]!=-1){ DisplayPath(G,s,p[s][t]); cout<<G.Vex[p[s][t]]<<”—>”; } }

int main(){ VexType start,destination; int u,v; AMGraph G; CreateAMGraph(G); Floyd(G); print(G); cout<<”请依次输入路径的起点与终点的名称：”; cin>>start>>destination; u=locatevex(G,start); v=locatevex(G,destination); DisplayPath(G,u,v); cout<<G.Vex[v]<<endl; cout<<”最短路径的长度为：”<<dist[u][v]<<endl; cout<<endl; return 0; } / 4 8 0 1 2 3 0 1 1 0 3 4 1 2 9 1 3 2 2 0 3 2 1 5 2 3 8 3 2 6 0 2 /

时间复杂度，优化方法见视频。
<a name="yJQA0"></a>
# 三：Bellman-Ford算法
贝尔曼福特算法，用于处理存在负权边，但不存在负环（回路权值之和为负）时的情况。他的优点是边的权值可以是负数，实现简单，缺点是时间复杂度较高，但同样，该算法存在若干优化可以提升效率。
<a name="Z9uIY"></a>
## 算法步骤：

1. 数据结构，因为要对边进行松弛操作，所以采用边集数组存储，每条边三个域，分别代表两端点ab和边权w。
1. 松弛操作：对所有边j（a,b,w），若dis[e[j].b]>dis[e[j].a]+e[j].w,若松弛，令dis[e[j].b]=dis[e[j].a]+e[j].w。其中dis[v]表示从源点到节点v的最短路径长度。
1. 重复松弛操作n-1次
1. 负环判定，也就是在进行一次松弛操作，若仍可松弛则说明有负环。
```cpp
#include<iostream>
#include<cstring>
using namespace std;
struct node{
    int a,b,w;
}e[210];
int dis[110];
int n,m,cnt=0;

void add(int a,int b,int w){
    e[cnt].a=a;
    e[cnt].b=b;
    e[cnt++].w=w;
}

bool bellman_ford(int u){//求源点u到其它顶点的最短路径长度，判负环 
    memset(dis,0x3f,sizeof(dis));
    dis[u]=0;
    for(int i=1;i<n;i++){//执行n-1次
        bool flag=false;
        for(int j=0;j<m;j++)//边数m或cnt
            if(dis[e[j].b]>dis[e[j].a]+e[j].w){
                dis[e[j].b]=dis[e[j].a]+e[j].w;
                flag=true;
            }
        if(!flag)
            return false;
    }
    for(int j=0;j<m;j++)//再执行1次，还能松弛说明有环
        if(dis[e[j].b]>dis[e[j].a]+e[j].w)
            return true;
    return false;
}

void print(){//输出源点到其它节点的最短距离 
    cout<<"最短距离："<<endl; 
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    cout<<endl;
}

int main(){
    int a,b,w;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b>>w;
        add(a,b,w);
    }
    if(bellman_ford(1))//判断负环
        cout<<"有负环！"<<endl;
    else
        print();    
    return 0;
}
/*测试数据1 
5 8
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
3 5 1
4 3 2
4 5 4
*/
/*测试数据2，有负环 
4 4
1 2 3
2 3 -4
3 4 2
4 2 1
*/

优化见视频

四：SPFA算法

对于贝尔曼福特的两种优化方式，我们更常用的是队列优化方法，他有自己的名字，叫SPFA算法，通常用于求解含负边权的单源最短路径以及判负环。

算法步骤：

创建一个队列，首先源点u入队，标记u在队列中，u的入队次数加一。
松弛操作，取出头结点x，标记x不在队列中。扫描x的所有出边i(x,v,w)，如果dis[v]>dis[x]+e[i].w，若松弛，令dis[v]=dis[x]+e[i].w。如果节点v不在队列中，判断v的入队次数加一后大于或等于n，则说明有负环，退出；否则v入队，标记v在队列中。
重复松弛操作。 ```cpp
include
include
include
using namespace std; const int maxn=505,maxe=100001; int n,m,cnt; int head[maxn],dis[maxn],sum[maxn]; bool vis[maxn];//标记是否在队列中 struct node{ int to,next,w; }e[maxe];

void add(int u,int v,int w){ e[cnt].to=v; e[cnt].next=head[u]; e[cnt].w=w;
head[u]=cnt++; }

bool spfa(int u){ queueq; memset(vis,0,sizeof(vis));//标记是否在队列中 memset(sum,0,sizeof(sum));//统计入队的次数 memset(dis,0x3f,sizeof(dis)); vis[u]=1; dis[u]=0; sum[u]++; q.push(u); while(!q.empty()){ int x=q.front(); q.pop(); vis[x]=0; for(int i=head[x];~i;i=e[i].next){ int v=e[i].to; if(dis[v]>dis[x]+e[i].w){ dis[v]=dis[x]+e[i].w; if(!vis[v]){ if(++sum[v]>=n) return true; vis[v]=1; q.push(v); } } } } return false; }

void print(){//输出源点到其它节点的最短距离 cout<<”最短距离：”<<endl; for(int i=1;i<=n;i++) cout<<dis[i]<<” “; cout<<endl; }

int main(){ cnt=0; cin>>n>>m; memset(head,-1,sizeof(head)); int u,v,w; for(int i=1;i<=m;i++){ cin>>u>>v>>w; add(u,v,w); } if(spfa(1)) cout<<”有负环！”<<endl; else print(); return 0; } /测试数据1 5 8 1 2 2 1 3 5 2 3 2 2 4 6 3 4 7 3 5 1 4 3 2 4 5 4 / /测试数据2，有负环 4 4 1 2 3 2 3 -4 3 4 2 4 2 1 /

``` 算法优化：SLF和LLL。

安排是否改变？

算法入门

四种最短路径算法-Dijkstra，Floyd，Bellman-ford，SPFA

一：Dijkstra算法（迪科斯彻算法）

算法步骤：

二：Floyd算法（弗洛伊德算法）

算法步骤：

include

include

四：SPFA算法

算法步骤：

include

include

include