本文所贴示的伪代码均来源《算法导论》，本文只是对其中《所有结点对的最短路径问题》章节的简单总结，许多数学证明过程已忽略。

对于给定有向图G=(V,E)理论上，我们可以使用|V|次单源最短路径算法来解决所有结点对之间的最短路径问。但除此之外，我们可以利用动态规划来解决此问题(因为一条最短路径的子结构也包含了最短路径).

一、基础解法

最短路径的结构:

对于有向图G=(V,E)的所有结点对的最短路径问题，可以证明一条最短路径的所有子路径都是最短路径。假定用邻接矩阵来表示输入图，即W=(  ). 考虑从结点i到结点j的一条最短路径p，假定p至多包含m条边，还假定没有权重为负值的环路，且m为有限值。

 

如果i=j，则p的权重为0且不包含任何边。如果结点i和j不同，则可以将其分解为i~k->j,其中路径i~k(用p’表示)至多包含m-1条边。可以证明，p’是从结点i到k的一条最短路径。因此，δ(i,j)=δ(i,k)+  。

 

对所有结点对最短路径问题的递归解

现在假设) 为从结点i到结点j至多包含m条路边的任意路径中的最小权重。当m=0时，从结点i到j之间存在一条没有边的路径当且仅当i=j。因此有



对于m>=1,我们需要计算的 是 的最小值和从i到j最多由m条边组成的任意路径的最小权重。我们通过对j的所有可能前驱k进行检查来获得该值，因此递归定义：



因为对于所有的j有  ，所以上述等式后面的式子成立。

 

但是真正的最短路径权重δ(i,j)是多少呢?如果图G不包含权重为负值的环路，则对于每一结点i和j，如果δ(i,j)<∞,从i到j之间存在一条最短路径。由于该路径是简单路径，最多包含n-1条边，从结点i到结点j由多于n-1条边构成的路径不可能比前者更短。因此，真正的最短路径权重可以由下面公式得出:



自底向上计算最短路径

根据输入矩阵W=(  ),现在可以计算出矩阵序列 、 、… ,其中对于m=1，2…n-1有 =  ，最后的矩阵 包含的是最短路径的实际权重。注意，对于所有的结点i和j， = (  ) , 因此  。

算法的核心伪代码如下：



 

二、Floyd-Warshall算法

在Floyd算法中，对一条最短路径的描述和上文稍有不同。Floyd算法考虑的是一条最短路径的中间结点。这里，简单路径p=<v0,v1…vl>上的中间结点是指p上除了v1和vl之外的所有结点。

Floyd算法依赖于下面的观察，假定图G的所有结点为V={1,2…n}；考虑到其中的一个子集{1,2…k},这里k是某个小于n的整数，并且设p为其中权重最小的路径(路径p是简单路径)。Floyd算法利用了路径p和从i到j之间中间结点均取自集合{1,2,…k-1}的最短路径之间的关系。该关系依赖于结点k是否是路径p上的一个中间结点。

·如果结点k不是路径p上的中间结点，则路径p上的所有中间结点一定属于集合{1,2…k-1};所以从结点i到j的中间结点取自{1,2…k}的最短路径也是结点i到j的中间结点取自{1,2…k-1}的最短路径；

·如果结点k是路径p上的中间结点，则路径p可以表示为i~k~j；其中i~k为路径p1，k~j为路径p2.显然，路径p1上的所有中间结点必定在{1,2…k-1}中，自然，p1是从结点i到k的中间结点位于{1,2…k-1}的最短路径。对于p2实际上也是同理，很容易退出，p2也是从结点k到j上的中间结点位于{1,2,…k-1}的一条最短路径；

于是，我们可以得到此问题的递归解：

                                       

其中 表示从i到j的中间结点都属于集合{1,2…k}的一条最短路径的权重。

由此，可以很容易得到Floyd算法的伪代码(自底向上的DP方法)



 

构建一条最短路径

在Floyd算法中，可以有许多不同的方法来构建最短路径，一种办法是先计算最短路径的权重矩阵D，然后用D来构造前驱矩阵Π。

另外，我们可以计算矩阵 的同时计算前驱矩阵Π。具体来说，我们将计算一个矩阵序列 、 、… ,并且定义  为从节点i到k的一条所有中间结点都取自集合{1，2…k}的最短路径上的j的前驱结点。

这里可以推出 的一个递推式，当k=0时，从i到j的一条最短路径没有中间结点，因此

                                                  

对于k>=1,如果考虑路径i~k~j,这里k != j，则所选择的结点j的前驱与我们选择的从结点k到j的一条中间结点全部取自集合{1，2…k-1}的最短路径上的前驱相同。如果不含中间结点的话，所选择的结点j的前驱和所选择的从结点i到j的一条中间结点全部出自集合{1,2…k-1}的最短路径的前驱是一样的。因此有：

                                

这里，只要把矩阵Π带入到Floyd算法流程中，与矩阵D一同计算即可。

 

 

 

 

Dijkstra算法可以说基本上每一本有讲到图的最短路径的书上都会有的一个算法，但基本上都是讲原理和伪代码，今天自己用Java代码给实现了一下，记录在此。
Dijkstra算法只是解决某些图的最短路径问题，这些图需要满足以下条件：权值非负、有向图。并且该算法只适用于求单源点最短路径，即起始点只是固定的某一个点，当然了，如果想求多源点最短路径，多用几次Dijkstra算法也是能求出来的。
该算法的原理就是：先处理源点，更新一下从源点到每个点的距离以及前结点信息，完后源点放到“已处理”组，从“未处理”组再找一个距离起点最近的点，看下是否有些点的路径在经过这个点后比原来的路径更短了，如果是，那么更新下距离以及前结点信息，如果否，不作操作，完后此点也放入“已处理”组，循环直到所有点都处理完。下面上代码：（最终打印路径的时候偷懒了一下没有把路径倒过来打印）
package classic;

import java.util.Scanner;

public class Dijkstra {

	public static int start = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("输入点和边的数目:");
		int V = sc.nextInt();//总共有多少个点
		int E = sc.nextInt();//总共有多少个边
		
		int[][] G = new int[V][V];//用来存放图的信息
		int[] d = new int[V];//用来存放从起点到每个点的最短路径长度
		int[] pre = new int[V];//用来存放每个点在其最短路径上的前一个结点
		boolean[] used = new boolean[V];
		
		System.out.println("依次输入每条边的起点、终点和权值:(点的编号从0开始)");
		for(int i=0; i<E; i++){
			G[sc.nextInt()][sc.nextInt()] = sc.nextInt();
		}

		for(int i=0; i<V; i++){//初始化d
			pre[i] = start;
			if(i==start){
				d[i] = 0;
				continue;
			}
			if(G[start][i]==0)
				d[i] = Integer.MAX_VALUE/E;
			else{
				d[i] = G[start][i];
			}	
		}

		int cur = 0;
		used[start] = true;

		while(cur<V){
			int minDis = Integer.MAX_VALUE/E;
			int minIndex = 0;
			for(int i=0; i<V; i++){//每次取d[i]最小的那个点
				if(!used[i] && d[i]<minDis){
					minDis = d[i];
					minIndex = i;
				}
			}
			used[minIndex] = true;
			for(int i=0; i<V; i++){
				if(G[minIndex][i]>0 && d[i]>d[minIndex]+G[minIndex][i]){
					d[i] = d[minIndex]+G[minIndex][i];
					pre[i] = minIndex;
				}
			}
			cur++;
		}
		for(int i=0; i<V; i++){
			System.out.println("起点"+start+"到点"+i+"的最短路径长度为:"+d[i]);
			System.out.println("最短路径为:");
			int curv = i;
			System.out.print(i+"<-");
			while(true){
				curv = pre[curv];
				if(curv == start)
					break;
				System.out.print(curv+"<-");
			}
			System.out.println(start);
		}
		sc.close();
	}
}



 

Floyd算法求有向图两点间最短距离
问题描述
用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵），按实验报告模板编写算法。


算法描述
在计算两点之间的最短路径时，如果两点之间存在其他的点，那么可以将最短路径的情况分为两类，经过某个点和不经过这个点。那么在求有向图中ab两点的最短路径时，遍历剩下的点，比较在a到b的路径中是经过Vi距离短还是不经过Vi距离短（Vi是除了ab的点）
核心代码
int floyd()
{
	int i,j,k;
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(a[i][k]+a[k][j]==min(a[i][j],a[i][k]+a[k][j]))
				{
					a[i][j]=a[i][k]+a[k][j];
					p[i][j]=k;
				}	
			}
		}
	}
 } 
 //数组a[I][J]为IJ之间的距离，无直接相连则距离无穷大
 //数组p[I][J]为IJ之间的最短路径上，从I出发要经过的下一个点

git源码
https://github.com/1651928813/Pepsi_juice.git

作业二文件夹

 1. Dijkstra算法:解决单源最短路径无负边

//=============算法思路====================
//1:邻接矩阵：一般不超过1000，无向边和有向边的区别
//2：邻接表（用链表），无向边和有向边的区别
//2.1：为了简便，vector(变长数组）
//3:Dijkstra算法
//3.1:Di伪代码
//G为图，一般设为全局变量；数据d为源点到各点的最短路径长度，s为起点
//D(G,D[],S)
//{
//初始化
//for(循环n次)
//{
//    u为D[u]中最小的还未被访问的顶点的标号；
//    设u已访问
//        for（以u为出发能到达的所有顶点V）
//    {
//        if(v未被访问&&以u为中介点使s到顶点v的最短路径更优）
//           优化d[v];
//             pre[v]=u;//记录v的前驱顶点是u//老是思考的一个问题：边界情况呢？
//4：怎么记录最短路径？上面可以进行优化的隐含信息：使d[v]变小的情况为让u作为s到v最短路径的前一个节点。
//4.1:记录v的前驱节点，pre[],第一个节点是没有前驱节点，初始化为自己
//4.2:然后递归找最短路径
//5:有多条最短路径：找第二标尺
//5.1：每一条边再加一个边权，最短路径的情况下求最小花费
//5.1.1:要判断最短路径相等的情况下，进行最小花费的判断
//5.2:每一个点增加一个点权（例如每个城市收集的物资），在前面的情况下求点权最大
//5.1.1:要判断最短路径相等的情况下，进行最大权值的判断
//5.3：有多少条最短路径
//5.3.1：更新的情况下：用num[u]代替num[v],表示最短路径（s->v)与(s->u)相同
//5.3.2：相等的情况：那么为num[v]+num[u],表示到达该点有多条路径
//}
//=============算法改进====================
//Dj+DFS
//1:先用DJ记录下最短路径;
//1.1:有可能有多个前驱节点：所以设置为vector<int>pre[MAXV]
//2:遍历最短路径（递归树），找到第二标尺最优的路径
//2.1：怎么写DFS函数：
//2.1.1:作为全局变量的第二标尺optValue
//2.1.2:记录最有路径（使用vector存储）
//2.1.3:临时记录DFS遍历叶子节点时的路径tempPath(使用vector存储）
//2.2:思路：
//2.2.1:递归边界（到达起点，也就是递归树的叶子节点）
//2.2.2:此时tempPath中存放了路径，再把起点加入，进行第二标尺的计算，与optValue进行比较
//2.3:递归式，遍历pre[v]的所有节点进行递归
//2.4:怎么生成tempPath
//2.4.1:访问当前节点v时把v加入
//2.4.2:遍历pre[v]进行递归
//2.4.3:所有节点全部遍历完之后删除v
//=============算法改进====================
//=============算法思路====================
#include <iostream>
#include <algorithm>
#include<vector>
#include<cstdio>
using namespace std;
//定义MAXV为最大顶点数，INF为一个很大的数
const int MAXV = 1000;
const int INF = 1000000000;//设为很大的数
//邻接矩阵版
int n,m,s, G[MAXV][MAXV];//n为顶点数,m为边数，s为起点，MAXV为最大顶点数
int d[MAXV],pre[MAXV];//起点到各点的距离
bool visit[MAXV] = { false };//点是否被访问
//DijkstraDFS新增的变量声明
//1:pre不进行初始化，那么起点的前驱节点设置为自己？
vector<int>pre[MAXV];//存放节点的前驱节点
int optValue;//第二标尺的最优值
vector<int>tempPath, path;//存放最佳路径和临时路径
void DijkstraDFS(int s) {
    //初始化
    fill(d, d + MAXV, INF);//需要加上头文件#include <algorithm>using namespace std;
    d[s] = 0;//自己到自己的距离为0
    /*visit[s] = true;这点在后面的循环中会进行执行*/
    for (int i = 0; i < n; i++)
    {
        int u = -1, min = INF;//u用记录最小值的下标，min用来记录最下值
        //利用一个for循环查找出当前最小的下标
        for (int j = 0; j < n; j++)
        {
            if (visit[j] == false && d[j] < min)
            {
                u = j;
                min = d[j];
            }
        }
        //防止出现不连通图，进行判断
        if (u == -1) { return; }
        /* else 有点多余，如果前面条件满足，就return了*/
        visit[u] = true;
        //以u出发到达的其他顶点v是否可以进行更新
        for (int v = 0; v < n; v++)
        {
            //还加了一个条件：if(G[u][v]!=INF//说明有边
            if (visit[v] == false && G[u][v] != INF  )
            {
                .if (d[u] + G[u][v] < d[v])
                {
                    d[v] = d[u] + G[u][v];
                    //进行清空
                    pre[v].clear();
                    pre[v].push_back(u);//把u加入前驱节点
                }
                else if (d[u] + G[u][v] = d[v])
                {
                    pre[v].push_back(u);
                }
                
               
            }
        }
    }
}
void DFS(int v)
{
    if (v == s) {
        tempPath.push_back(v);
        int value=0;//用来记录tempPath中的值，判断是否要对optValue进行更新
        //计算value值
        //边权之和；点权之和

        if (value优于optValue) {
            optValue = value; path = tempPath;
        }
        tempPath.pop_back(v);
        //要进行返回，递归边界
        return;
    }
    tempPath.push_back(v);
    for (int i = 0; i < pre[v].size(); i++)
    {
        DFS(pre[v][i]);
    }
    tempPath.pop_back(v);
}
void Dijkstra(int s)//s为起点
{
    //初始化
    fill(d, d + MAXV, INF);//需要加上头文件#include <algorithm>using namespace std;
    d[s] = 0;//自己到自己的距离为0
    /*visit[s] = true;这点在后面的循环中会进行执行*/
    for (int i = 0; i < n; i++)
    {
        int u = -1, min = INF;//u用记录最小值的下标，min用来记录最下值
        //利用一个for循环查找出当前最小的下标
        for (int j = 0; j < n; j++)
        {
            if (visit[j] == false && d[j] < min)
            {
                u = j;
                min = d[j];
            }
        }
        //防止出现不连通图，进行判断
        if (u == -1) { return; }
        /* else 有点多余，如果前面条件满足，就return了*/
        visit[u] = true;
        //以u出发到达的其他顶点v是否可以进行更新
        for (int v = 0; v < n; v++)
        {
            //还加了一个条件：if(G[u][v]!=INF//说明有边
            if (visit[v] == false &&G[u][v]!=INF &&d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] + G[u][v];
                pre[v] = u;//记录v的前驱节点是u
            }
        }
    }
    
}
void DFS(int s, int v)//输出起点到终点的最短路径
{
    //递归边界
    if (s == v) { printf("%d\n", s); return; }
    DFS(s, pre[v]);//往前递归
    //回来时的处理
    printf("%d\n", v);//每一层回来输出每一层的顶点号
}
//邻接表法
//结构构造函数初始化：与c++和java中构造函数类似
struct node {
    int v;//变得终点号
    int w;//边权
    //定义无参构造函数
    node(){}
    //构造函数简化成一行
    node(int _v, int _w) :v(_v), w(_w) {}
};
//算法初始化和找u的过程是一样的，只是查找以u的中介的其他顶点更新不一样
vector<node>adj[MAXV];//图G,adj[u]存放从顶点u出发可以到达的所有顶点
void Dijkstra1(int s)//s为起点
{
    //初始化
    fill(d, d + MAXV, INF);//需要加上头文件#include <algorithm>using namespace std;
    d[s] = 0;//自己到自己的距离为0
    /*visit[s] = true;这点在后面的循环中会进行执行*/
    for (int i = 0; i < n; i++)
    {
        int u = -1, min = INF;//u用记录最小值的下标，min用来记录最下值
        //利用一个for循环查找出当前最小的下标
        for (int j = 0; j < n; j++)
        {
            if (visit[j] == false && d[j] < min)
            {
                u = j;
                min = d[j];
            }
        }
        //防止出现不连通图，进行判断
        if (u == -1) { return; }
        /* else 有点多余，如果前面条件满足，就return了*/
        visit[u] = true;
        //以u出发到达的其他顶点v是否可以进行更新
        //adj[u].size()获取u所连的边的个数
        for (int j = 0; j < adj[u].size(); j++)
        {
            //通过邻接表直接获得u能到达的顶点v
            int v = adj[u][j].v;//adj中储存了各条边的情况
            //还加了一个条件：if(G[u][v]!=INF//说明有边
            if (visit[v] == false && d[u]+ adj[u][j].w< d[v])
            {
                d[v] = d[u] + adj[u][j].w;
            }
        }
    }

}
//对应DJ+DFS:1.1:找最短路径，有可能有多个前驱节点：所以设置为vector<int>pre[MAXV]
void Dj(int v)
{
	fill(d, d + MAXV, INF);
	d[v] = 0;
	for (int i = 0; i < n; i++)
	{
		int u = -1, min = INF;
		for (int j = 0; j < n; j++)
		{
			if (vis[j] == false && d[j] < min)
			{
				u = j;
				min = d[j];
			}
		}
		if (u == -1)return;
		vis[u] = true;
		for (int k = 0; k < n; k++)
		{
			if (vis[k] == false && d[u] + G[u][k] < d[k])
			{
				//d[u]要进行更新
				d[k] = d[u] + G[u][k];
				pre[k].clear();
				pre[k].push_back(u);
			}
			else if (vis[k] == false && d[u] + G[u][k] == d[k])\
			{
				pre[k].push_back(u);

			}
		}
	}
}
int main()
{
    int u, v, w;
    scanf("%d%d%d", &n, &m, &s);//顶点个数、边数、起点编号
    fill(G[0], G[0] + MAXV * MAXV, INF);//初始化图
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);//输入u、v以及u->v的边权
        G[u][v] = w;
    }
    Dijkstra(s);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", d[i]);//输出所有顶点的最短距离
    }
    //for (int i = 0; i < n; i++)
    //{
    //    printf("%d", pre[i]);//输出所有顶点的最短距离
    //}

    return 0;
}





BF：可以解决负边问题

2.1:[PAT1003]
//BF算法：解决单源路径最短问题（可处理负边权的问题）
//思路：
//1.1对图中的边进行V-1次遍历(用最小生成树理解松弛操作不会超过V-1:最小生成树最多不会超过V个，并且起点已经为d[s]=0,不能再进行优化)，对每一个边，看是否可以进行优化
//1.2最后再检查一下是否有负环
//2：解决实际问题：有多条路径最短的问题：记录num值的时候，为了防止重复的值发生，则需要重新记录（并且用set进行存储）
//出现的问题：
#include <iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int maxv = 500;
const int INF = 1000000000;
int n, m;//定义点和边
struct node{
    int v;//边的终点编号
    int w;//边权
    node(int v_, int w_) :v(v_), w(w_) {};
};
vector<node>adj[maxv];//图G的邻接表
int weight[maxv],num[maxv],w1[maxv];//用来存放个点的权值和数量,w1是用来存放最大的点权
set<int>pre[maxv];//记录前驱的数组
int d[maxv];

void kus(int s) {
    //初始化
    fill(num, num + maxv, 0);
    fill(d, d + maxv, INF);
    d[0] = 0;
    num[s] = 1;
    w1[s] = weight[s];//这一步忘记加入
    for (int i = 0; i < n - 1; i++)//遍历n-1次
    {
        //每次遍历每一条边
        for(int u=0;u<n;u++)
            for (int j = 0; j < adj[u].size(); j++)//看是否可以以u为中介可以进行优化
            {
                int v = adj[u][j].v;//邻接边的顶点
                int dis = adj[u][j].w;//邻接边的边权
                if (d[u] + dis < d[v])//可以进行优化:是对顶点进行优化
                {
                    d[v] = d[u] + adj[u][j].w;//覆盖d
                    w1[v] = w1[u] + weight[v];//优化边的权值
                    num[v] = num[u];//直接覆盖
                    pre[v].clear();
                    pre[v].insert(u);
                }
                else if (d[u] + dis == d[v])//找到路径相等
                {
                    if(w1[u] + weight[v]>w1[v])w1[v] = w1[u] + weight[v];//优化边的权值
                    pre[v].insert(u);//一步步进行优化
                    
                                                                         
              //此时有可能会有重复的节点，所以需要重新计算
                    num[v] = 0;
                set<int>::iterator it;
                for (it = pre[v].begin(); it != pre[v].end(); it++)
                {
                    num[v] += num[*it];
                }
                }
            }
    }

}
int main()
{
    int s, e;
    scanf_s("%d%d%d%d", &n, &m, &s, &e);
    for (int i = 0; i < n; i++)scanf_s("%d", &weight[i]);
    int s1, s2, s3;
    for (int i = 0; i < m; i++)
    {
        scanf_s("%d%d%d", &s1, &s2, &s3);
        adj[s1].push_back(node(s2,s3));
        adj[s2].push_back(node(s1, s3));
    }
    kus(s);//传入起点进去
    printf("%d %d", num[e], w1[e]);
    return 0;
}


SPFA

3.1:[PAT1003]


//思路： SPFA(shortest path faster algorithm)对BF进行改进，BF每次都要进行全部边的判断
//1：只有当某个顶点的d[u]值改变时，从它出发的邻接点的v的d[v]的值才有可能改变
//1.1：设置一个队列，每次将队首元素取出，然后对从u出发的所有边u-》v进行松弛操作，判断是否可以，如果可行，判断v是否在队列中，不在则加入队列，直到队列为空
//错误总结：1：邻接矩阵储存图的意思，怎么获取顶点值和边权
//2:SPFA是由BF改进来的，所以对num数组进行优化时的情况也要考虑是否会进行重复计算
//3:当路径相等时相当于也进行了优化
#include<cstring>//memset在这个头文件中
#include <iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;
int n, m;
const int maxv=510;
const int INF = 1000000000;
int weight[maxv];
struct node {//熟悉邻接表储存图的意思，什么时候获取顶点值，什么时候
    int s;//s为顶点
    int v;//表示边权：单源最短路径问题
    node(int s1, int v1) :s(s1), v(v1) {};
};
vector<node>adj[maxv];
int num[maxv], w[maxv],d[maxv];
bool inq[maxv];
set<int>pre[maxv];//记录前驱的数组
void SPFA(int s)
{
    memset(num, 0, sizeof(num));
    memset(w, 0, sizeof(w));
    memset(inq, false, sizeof(inq));
    fill(d, d + maxv, INF);
    //源点入队
    queue<int>q;
    q.push(s);
    d[s] = 0;
    w[s] = weight[s];//权值初始化
    num[s]++;
    inq[s] = true;
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int j = 0; j < adj[v].size(); j++)
        {
            int q1 = adj[v][j].s;//获取点值
            int w2 = adj[v][j].v;//获取边权
            //进行松弛操作
            if (d[v] + w2 < d[q1])
            {
                d[q1] = d[v] + w2;
                num[q1] = num[v];//数量覆盖
                w[q1] = w[v] + weight[q1];
                pre[q1].clear();
                pre[q1].insert(v);
                //要进行判断是否在队列中
                if (!inq[q1]);
                {
                    q.push(adj[v][j].s);
                     inq[q1] = true;
                }
                
                
            }
            else if (d[v] + w2 == d[q1])
            {
                if (w[q1] < w[v] + weight[q1])
                {
                    w[q1] = w[v] + weight[q1];
                }
                pre[q1].insert(v);
                /*num[q1] += num[v];*/
                num[q1] = 0;
                //防止反复累计的值
                set<int>::iterator it;
                for (it = pre[q1].begin(); it != pre[q1].end(); it++)
                {
                    num[q1] += num[*it];
                }
                //这段也是至关重要的：此时也相当于进行了优化
                if (!inq[q1]);
                {
                q.push(adj[v][j].s);
                inq[q1] = true;
                }
            }
        }
    }

}
int main()
{
    int s, e;
    cin >> n >> m>>s>>e;
    for (int i = 0; i < n; i++)
    {
        cin >> weight[i];
    }
    int s1, e1, w1;
    for (int i = 0; i < m; i++)
    {
        cin >> s1>>e1>>w1;
        //这里是个双向图：用邻接表储存的方法
        adj[s1].push_back(node(e1, w1));
        adj[e1].push_back(node(s1, w1));
    }
    SPFA(s);
    cout << num[e] <<" "<< w[e];
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件


4:Floyd:解决全源路径最短问题
// Floyd.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//Floyd算法目的：解决全源最短路径问题：时间复杂度为O(n^3)
//Floyd算法思路：
//1:枚举每个顶点
//2:以每个顶点为中介，判断是否可以进行优化
#include <iostream>
#include<algorithm>
using namespace std;
//定义全局变量
int n, m;//定义点数和边数
const int  MAXV= 200;//把顶点数限制在200以内
const int INF = 100000000;
int dis[MAXV][MAXV];//距离数组：表示顶点i到j的距离
//不需要定义是否访问
//F算法
void Floyd()
{
    for (int k = 0; k < n; k++)//枚举顶点：注意不要放到内层循环
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                //经过以k为中介，i到j的距离能不能缩短
                if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
}
int main()
{
    //输入顶点、边数
    
    scanf_s("%d%d", &n, &m);
    //初始化
    //1:数组进行全部初始化
    //初始化的格式写错了：应该为dis[0]
    fill(dis[0], dis[0] + MAXV * MAXV, INF);
    //2：初始距离设为0；
    //:2：自己到自己的距离初始化为0
    for (int i = 0; i < n; i++)dis[i][i] = 0;
    /*for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        { dis[i][j] = 0;}         
    }*/
    //输入边的信息
    int u, v, w;//输入顶点和边的权值
    for (int i = 0; i < m; i++)
    {
        scanf_s("%d%d%d", &u, &v,&w);
        //为什么还要定义距离矩阵呢？不能直接在邻接矩阵上进行操作吗？
        //没必要定义两个数组，直接在矩阵上进行操作
        dis[u][v] = w;
    }
    Floyd();//入口
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", dis[i][j]);
        } 
        printf("\n");

    }
    return 0;


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件