精华内容
下载资源
问答
  • 本文所贴示的伪代码均来源《算法导论》,本文只是对其中《所有结点对最短路径问题》章节简单总结,许多数学证明过程已忽略。 对于给定有向图G=(V,E)理论上,我们可以使用|V|次单源最短路径算法来解决所有结点对...

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

    对于给定有向图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算法只是解决某些图的最短路径问题,这些图需要满足以下条件:权值非负、有向图。并且该算法只适用于求单源点最短路径,即起始点只是固定的某一个点,当然了,如果想求多源点最短路径,多用几次Dijkstra算法...

    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距离短...

    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:邻接矩阵:一般不超过1000,无向边和有向区别 //2:邻接表(用链表),无向边和有向区别 //2.1:为了简便,vector(变长数组) //3:Dijkstra算法 //3.1:Di伪代码 //G为,一般设为全局变量;数据d为源点...
    
     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;
    }
    
    
    
    
    1. 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;
    }
    
    1. 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 文件
    
    
    展开全文
  • 现有一个有向无权。如下所示: 问题:使用某个顶点s作为输入参数,找出从s到所有其他顶点最短路径。 说明:因为是无权,因此我们可以为每台边赋值为1。这里选择v3为s作为起点。 问题分析 此时立刻可以...
  • 其实最短路径排序,就是对整个有向图进行一次搜索,此方法也被称为广度优先搜索,类似于树层序遍历。 这里也是提供的伪代码,注释很清晰,如有不懂请参考数据结构与算法C语言描述版。 //伪代...
  • 常用算法代码

    2017-09-11 11:26:53
    | 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) 8 | 有向图最小点基(邻接阵)O(N^2) 9 | FLOYD 求最小环 9 | 2-SAT 问题 9 Network 网络流 11 | 二分图匹配(匈牙利算法 DFS 实现) 11 | 二分图匹配(匈牙利算法 ...
  • 单源最短路径通用解法—BellmanFord

    千次阅读 2010-11-14 00:06:00
    问题:在可能存在负边的情况下,计算有向图中某个起点s到其它所有点的最小距离。设w[i][j]为点i到j的边的权值,G为图的邻接表表示。BellmanFord算法可以用来求s到所有点的最小距离,当图中存在负边回路时,该...
  • Dijkstra算法Java实现

    千次阅读 2013-12-09 17:39:17
    迪科斯彻(Dijkstra)算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。 在一个有向非负权重的图中,可以知道如AC>AB,这AC+CB>AB,这一不等式有点贪心算法的思想,每次选择时...
  • G为连通有向图,f是u-->v路径上已有流量,Gf为残留网络 伪代码如下: 1 for each edge(u,v)属于E(G) 2 do f[u,v]=0 3 f[v,u]=0 4 while there exists a path p from s to t in the residual network Gf 5 do...
  • 弗洛伊德算法是解决任意两点间最短路径问题的一种算法,可以处理无向图或者有向图(可以有负权重,但不可能会存在负权重回路)最短路径问题。 弗洛伊德算法与其他求最短路径算法异同 Floyd算法与迪杰斯特拉...
  • 多态性语言具有灵活、抽象、行为共享、代码共享优势,很好解决了应用程序函数同名问题。 5、String是最基本数据类型吗?  基本数据类型包括byte、int、char、long、float、double、boolean和short。  java....
  • 弗洛伊德算法,是解决任意两点间最短路径一种算法,可以正确处理无向图或有向图(可以有负权重,但不可存在负权回路)最短路径问题 Floyd算法与迪杰斯特拉算法或贝尔曼福特算法相比,能够一次性求出任意两点...
  • Dijkstra算法

    2020-06-02 10:57:50
    Dijkstra算法 c++实现前言算法介绍《算法导论》伪代码 前言 第一次写博客哈,如果有不对地方...Dijkstra算法解决是带权重的有向图上单源最短路径问题,该算法要求所有边权重都为非负值。 《算法导论》伪代码 ...
  • Dijkstra算法 C++

    2018-07-15 09:20:00
    适用范围:解决无负权边的带权有向图或无向图的单源最短路问题2.算法思想:贪心思想,每次从当前结点出发走下一个权值最小的边。3.伪代码:令S={源点s + 已经确定了最短路径的顶点vi}对任一未收录的顶点v,定义dist...
  • 算法导论22.4-2

    千次阅读 2017-11-27 20:15:04
    请给出一个线性时间的算法,算法的输入为一个有向无环G=(V,E)G=(V,E)以及两个结点s和t,算法的输出是从结点s到结点t之前的简单路径的数量。 问题解答 由于除了s与t相等的情况外,每一条从u到v的路径必定经过u的...
  • 问题描述 一个含有n个点迷宫是一棵树(一个任意两点之间都恰好一条路径的向图)。每个点都一定概率成为这个迷宫入口和出口。 从这个迷宫走出去方法是从入口开始进行深度优先搜索。如果当前多个...
  • 4.4.2 加权有向图的数据结构 4.4.3 最短路径算法的理论基础 4.4.4 Dijkstra算法 4.4.5 无环加权有向图中的最短路径算法 4.4.6 一般加权有向图中的最短路径问题 4.4.7 展望 第5章 字符串 5.1 字符串排序 ...
  • 对于一个有向无圈DAG,其中顶点s入度为0,t出度为0,设计算法求s到t最长路径的长度,简述算法基本思想,写出伪代码并分析其时间复杂度 证明 安全边定理 最大流最小割定理 求单源点最短路径中,设源点s到...
  • 4.4.2 加权有向图的数据结构 414 4.4.3 最短路径算法的理论基础 420 4.4.4 Dijkstra算法 421 4.4.5 无环加权有向图中的最短路径算法 425 4.4.6 一般加权有向图中的最短路径问题 433 4.4.7 展望 445 第5...
  • 文章管理系统

    2014-12-06 10:19:22
    2.纠正后台文章编辑,获取编辑器图片无法获取网络图片路径问题 3.后台文章管理,标题后面加入是否含缩略图的图标 4.纠正后台文章编辑,保存远程图片到本地,如果缩略图是网络图片没纠正成本地路径的BUG 5.删除网站...
  • 修改程序源代码前请查看程序代码版权注释信息 2、官网关于本程序使用教程及操作技巧 后台应用中心可安装,模板、扫码打赏插件、手机版与电脑版智能管理插件、屏蔽复制与鼠标右键插件、老y文章系统数据迁移至...
  • 8、广告管理,可在现有广告位添加广告,同时针对相对路径不同层级的路径进行了优化,广告管理页面详细的介绍。 9、友情链接管理,可设置图片或文字类型的友链。 10、后台操作日志管理,记录了后台所有的操作记录...
  • 算法导论中文版

    2016-10-26 10:13:58
     24.2 有向无环单源最短路径问题  24.3 Dijkstra算法  24.4 差分约束和最短路径  24.5 最短路径性质证明  思考题  本章注记 第25章 所有结点对最短路径问题  25.1 最短路径和矩阵乘法  25.2...
  • C#微软培训教材(高清PDF)

    千次下载 热门讨论 2009-07-30 08:51:17
    18.2 在 C #代码中调用 C++和 VB 编写组件 .240 18.3 版 本 控 制 .249 18.4 代 码 优 化 .252 18.5 小 结 .254 第五部分 附 录 .255 附录 A 关 键 字.255 附录 B 错 误 码.256 附录 C .Net 名字空间...
  • C#微软培训资料

    2014-01-22 14:10:17
    18.2 在 C #代码中调用 C++和 VB 编写组件 .240 18.3 版 本 控 制 .249 18.4 代 码 优 化 .252 18.5 小 结 .254 第五部分 附 录 .255 附录 A 关 键 字.255 附录 B 错 误 码.256 附录 C .Net 名字空间...
  • 6.4.1 遍历有向图 6.4.2 传递闭包 6.4.3 DFS和垃圾收集 6.4.4 有向无环图 6.5 Java示例:深度优先查找 6.5.1 修饰模式 6.5.2 DFS引擎 6.5.3 模板方法设计模式 6.6 习题 基础题 创新题 程序设计 6.7 本章注记 第7章 ...
  • php高级开发教程说明

    2008-11-27 11:39:22
    容将针对大部分基本却是非常重要开发中实际问题进行讨论:改善代码质量以及基本设 计和文件管理的问题。陈述完这些后,我们创建一个应用程序接口( A P I),采取简单、实用 方式使你熟悉这一新思想,...
  • 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号常量 33 3.2.2 变量 33 3.3 整型...

空空如也

空空如也

1 2 3
收藏数 44
精华内容 17
关键字:

有向图的路径问题伪代码