精华内容
下载资源
问答
  • 研究生考研机试 最短路径 迪杰斯特拉算法
    2020-11-04 08:51:17

    研究生考研机试 最短路径 迪杰斯特拉算法

    题目描述
    N个城市,标号从0到N-1,M条道路,第K条道路(K从0开始)的长度为2^K,求编号为0的城市到其他城市的最短距离
    输入描述:
    第一行两个正整数N(2<=N<=100)M(M<=500),表示有N个城市,M条道路
    接下来M行两个整数,表示相连的两个城市的编号
    输出描述:
    N-1行,表示0号城市到其他城市的最短路,如果无法到达,输出-1,数值太大的以MOD 100000 的结果输出。
    示例1
    输入
    复制
    4 4
    1 2
    2 3
    1 3
    0 1
    输出
    复制
    8
    9
    11

    解题思路:第k条路径的长度会大于前k-1条路径的总和
    在图的初始化方面,进行优化,对于输出城市A,B,如果A,B之前已经连通,那么那么新的路径长度无效。

    #include<iostream>
    using namespace std;
    #include<vector>
    #include<queue>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<climits>
    int  dis[105];
    
    int father[105];
    int height[105];
    const int MAXN=INT_MAX;
    
    int n,m;
    
    void init(int n)
    {
    	memset(height,0,sizeof(height));
    	
    	for(int i=0;i<n;i++)
    		father[i]=i;
    }
    
    struct Point_distance{
    	int x;
    	int  distance;
        
    	Point_distance(int n,int d):x(n),distance(d){
    	}
    	
    		
    	bool operator<(const  Point_distance  & mm) const{
    		
    		return distance > mm.distance;
    		
    	}
    	
    
    };
    
    struct to_length{
    	int to;
    	int length;
    	to_length(int t,int l):to(t),length(l){}
    };
    
    int find(int x)
    {
    	if(x!=father[x])
    	  father[x]=find(father[x]);
    	return father[x];
    }
    void unionn(int x,int y)
    {
    	int xx=find(x);
    	int yy=find(y);
    	
    	if(xx!=yy)
    	{
    		if(height[xx]>height[yy])
    			{
    				father[yy]=xx;
    			}
    		else if(height[xx]<height[yy])
    		    father[xx]=yy;
    		    else {
    		    	father[yy]=xx;
    		    	height[xx]++;
    			}
    	}
    	
    }
    
    
    int main()
    {
         priority_queue<Point_distance> myqueue;
         
         vector<to_length> pp[105];//adjacency list
    
    //     memset(dis,0x09,sizeof(dis));
         
         
        
        
    //    cout<<dis[0];
    	cin>>n>>m;
    	int  k=1;
    	
    	init(n);
    	int x,y;
    	memset(pp,0,sizeof(pp));
    	
    	 for(int i=0;i<n;i++)
         dis[i]=MAXN;
    	for(int i=0;i<m;i++)
    	{
           cin>>x>>y;
           if(find(x)!=find(y))   //注意!!此题关键,见解析
           {
           	unionn(x,y);
           pp[x].push_back(to_length(y,k));
           pp[y].push_back(to_length(x,k));
    	   }
             
    	   k=(k*2)%100000;		
    	   
    	}
    	
    	dis[0]=0;
    	
    	myqueue.push(Point_distance(0,0));
    	
    	while(!myqueue.empty())  //dij()
    	{
    		int u=myqueue.top().x;
    		myqueue.pop();
    		
    		for(int i=0;i<pp[u].size();i++)
    		{
    			int v=pp[u][i].to;
    			int  length=pp[u][i].length;
    			if(dis[v]>dis[u]+length)
    			{
    				dis[v]=dis[u]+length;
    //				dis[v]=dis[v]%100000;
    				myqueue.push(Point_distance(v,dis[v]));
    			}
    		}
    		
    	}
    	
    	for(int i=1;i<n;i++)
    	{
    		if(dis[i]==MAXN)
    		cout<<"-1"<<endl;
    		else cout<<dis[i]%100000<<endl;
    	}
    	
    	return 0;
    }
    
    更多相关内容
  • 由于AOE网中的某些活动能够同时进行,故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。
  • 数据结构中的关键路径实现,可视化界面,迪杰斯特拉算法,和弗洛伊德算法
  • 总结最短路径算法关键先把已知最短路径顶点集...集中在加入时可以记录每个顶点的最短路径也可以在加入完毕 后回溯找到每个顶点的最短路径和权重 迪杰斯特拉算法用于求解一个有向图也 可以是无向图无向图是有向图的一种
  • 迪杰斯特拉算法及其堆优化

    千次阅读 2021-03-22 16:51:55
    迪杰斯特拉算法是一种求解图的单点最短路径的算法。 迪杰斯特拉算法的原理是 1.首先在没有中间节点的情况下,也就是直达路径中找到到达某点p的最短路径。易知,该路径一定是原点到点p的最短路径。将点p标记在vis数组...

    迪杰斯特拉算法及其堆优化

    迪杰斯特拉算法是一种求解图的单点最短路径的算法。
    一句话来说就是找最近点,更新相邻距离,再找最近点,更新相邻距离
    迪杰斯特拉算法的原理是
    1.首先在没有中间节点的情况下,也就是直达路径中找到到达某点p的最短路径。易知,该路径一定是原点到点p的最短路径。将点p标记在vis数组中,并将最短路径的值存在dist数组中。
    2.再对所有节点进行松弛操作,也就是下一个节点的最短路径有两种情况,一种是经过某个已知的最短路(就是被vis标记的最短路径),第二种情况是直达。所以,求解下一个最短路径就是求解递推公式
    dist[i]=min(dist[i] , map[i][now]+dist[now])
    now是上一个最短路径。
    3.找到最短的dist并标记在vis中,并迭代2,3步。
    总体来说,迪杰斯特拉算法是按从小到大的顺序求解到各个点的最短路径,每求出一个最短路径,下次循环时就判断所有的点(其实等同于没有求出最短路径的点)如果经过上一个已经求出最短路径的点,是否会出现更短的路径(这一步就成为松弛操作)。在遍历所有点的同时,找到没有求出最短路径的点中的最短路径,并保存。
    没有优化的迪杰斯特拉算法的时间复杂度为O(n*n)。
    下面是一张图解:
    在这里插入图片描述

    以下是参考代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define inf 0x7fffffff
    long long int dist[100100];
    int Map[1000][1000];
    int vis[1010];
    int main(){
    	int n,m,s;
    	while(~scanf("%d%d%d",&n,&m,&s)){
    		for( int i=1;i<=n;i++){
    			for( int j=1;j<=n;j++){
    				Map[i][j]=0x7fffffff;
    			}
    			dist[i]=0x7fffffff;
    		}
    		memset(vis,0,sizeof(vis));
    		for( int i=1;i<=m;i++){
    			int from,to,val;
    			cin>>from>>to>>val;
    			Map[from][to]=min(val,Map[from][to]);
    			Map[to][from]=min(val,Map[from][to]);	
    		}
    		dist[s]=0;
    		vis[s]=1;
    		int start=s;
    		for( int j=1;j<=n;j++){
    			int next, minn=0x7fffffff;;
    			for( int i=1;i<=n;i++){
    				if(Map[start][i]!=inf) {
    					dist[i]=min(dist[i],Map[start][i]+dist[start]);
    				}
    				if(vis[i]==0&&dist[i]<minn){
    					next=i;
    					minn=dist[i];
    				}	
    			}
    			
    			if(minn==inf)break;
    			start=next;
    			vis[start]=0;
    		}
    		for( int i=1;i<=n;i++){
    			cout<<dist[i];
    			if(i!=n) cout<<" ";
    		}
    		cout<<endl;
    		
    	}
    }
    

    对迪杰斯特拉算法的优化:
    上面的迪杰斯特拉算法主要缺陷是,每当找到一个最短路径,如果需要找下一个最短路径,就需要在完成松弛操作之后,遍历dist数组,寻找其中的最小值。遍历dist数组的时间复杂度为O(n)。
    如果图的边数为n*(n-1),那么每找到一个最小值,所要进行的松弛操作数就是n-1,这和遍历dist数组可以同时进行,算法优化的空间不大。
    然而,如果是稀疏图,每找到一个最小值,所要进行的松弛操作数就远小于n-1,这时就可以对算法进行优化。优化的关键是省去对dist的线性查找,如果每次可以直接返回dist中的最大值,就可以大大减小算法的时间复杂度。
    堆优化后的迪杰斯特拉算法复杂度为ElogE

    #include<bits/stdc++.h>
    using namespace std;
    #define inf 0x7fffffff
    struct p{
    	long long int to,val,next;
    };
    p edge[200100];
    long long int dist[100100];
    int vis[100100];
    int head[100100];
    int cnt;
    void add_edge( long long from,long long to,long long  val){
    	edge[++cnt].val=val;
    	edge[cnt].to=to;
    	edge[cnt].next=head[from];
    	head[from]=cnt;
    }
    struct node{
    	long long int from,val;
    	bool operator <(const node &a ) const{
    		return a.val<val;
    	}
    };
    int main(){
    	int n,m,s;
    	while(~scanf("%d%d%d",&n,&m,&s)){
    		cnt=0;
    		memset(edge,0,sizeof(edge));
    		for( int i=1;i<=n;i++){
    			dist[i]=1e12;
    			head[i]=0;
    			vis[i]=0;
    		}
    		for( int i=1;i<=m;i++) edge[i].val=1e12;
    		for( int i=1;i<=m;i++){
    			long long int from,to,val;
    			scanf("%lld%lld%lld",&from,&to,&val);
    			add_edge(from,to,val);
    		}
    		dist[s]=0;
    		priority_queue<node>q;
    		q.push({s,0});
    		while(!q.empty()){
    			node now=q.top();
    			q.pop();
    			if(vis[now.from]) continue;
    			vis[now.from]=1;
    			for( long long int  i=head[now.from];i!=0;i=edge[i].next){
    				int j=edge[i].to;
    				if(dist[now.from]+edge[i].val<dist[j]){//进行松弛操作
    					dist[j]=dist[now.from]+edge[i].val;
    					q.push({j,dist[j]});
    				}
    			}
    		}
    		for( int i=1;i<=n;i++){
    			printf("%lld ",dist[i]);
    		}
    		cout<<endl;	
    	}
    }
    

    迪杰斯特拉算法的优化可以总结为以下几步:
    1.将最短距离出队。
    2.进行松弛操作,并将成功松弛的点入队。

    展开全文
  • 前言需求今天我们学习的是迪杰斯特拉算法(最短路径),我们还是从一个场景里引入看看战争时期,胜利乡有7个村庄(A, B, C, D, E, F, G)有一名邮差需要你的帮忙:从G点出发,分别把邮件分别送到 A, B, C , D, E, F 六个...

    前言需求


    今天我们学习的是迪杰斯特拉算法(最短路径),我们还是从一个场景里引入看看

    图片.png

    战争时期,胜利乡有7个村庄(A, B, C, D, E, F, G)

    有一名邮差需要你的帮忙:从G点出发,分别把邮件分别送到 A, B, C , D, E, F 六个村庄

    问:如何计算出G村庄到 其它各个村庄的最短距离?

    1.各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里

    2.如果从其它点出发到各个点的最短距离又是多少?

    一、什么是迪杰斯特拉算法?

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法

    用于计算一个结点到其他结点的最短路径。 

    它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

    让我们回顾一下广度优先搜索的思想,可以看往期文章:图(广度优先与深度优先)

    图的广度优先搜索(Broad First Search)

    图片.png

    图的深度优先搜索(Depth First Search)

    图片.png

    迪杰斯特拉(Dijkstra)算法过程

    设置出发顶点为v,顶点集合V{v1,v2,vi...}

    v到V中各顶点的距离构成距离集合Dis,Dis{d1,d2,di...}

    Dis集合记录着v到图中各顶点的距离(到自身可以看作0,v到vi距离对应为di)

    步骤如下:

    • 从Dis中选择值最小的di并移出Dis集合同时移出V集合中对应的顶点vi,此时的v到vi即为最短路径
    • 更新Dis集合,更新规则为:比较v到V集合中顶点的距离值,与v通过vi到V集合中顶点的距离值,保留值较小的一个(同时也应该更新顶点的前驱节点为vi,表明是通过vi到达的)
    • 重复执行两步骤,直到最短路径顶点为目标顶点即可结束

    二、通过示例来认识算法

    迪杰斯特拉算法图解思路

    A、B、C、D、E、F、G 这些顶点,我们使用数组记录他们是否访问过

    图片.png

    根据示意图,画出他们的邻接矩阵

    image.png

    按照要求,假如从G顶点出发,如图所示能连接的顶点有:A、B、E、F

    image.png

    这时我们,使用数组记录A、B、E、F的前驱顶点指向G顶点下标

    image.png

    接下来我们使用数组记录,同时判断A、B、E、F与G顶点的连接权值

    image.png

    那么这个时候,我们以最小权值:A,作为新访问节点,继续遍历操作

    迪杰斯特拉算法思路

    1.使用邻接矩阵来表示图所之间连接关系与权重值

    图片.png
    图片.png

    //使用邻接矩阵描述权重值表示0 代表无
    int[][] weight = new int[][]{
     {0,5,7,0,0,0,0},
     {5,0,0,9,0,0,3},
     {7,0,0,0,8,0,0},
     {0,9,0,0,0,4,0},
     {0,0,8,0,0,5,4},
     {0,0,0,4,5,0,6},
     {2,3,0,0,4,6,0}
    };

    2.需要一个存放顶点的char数组

    //char[] 数组存放顶点个数
    char[] data = new char[]{'A','B','C','D','E','F','G'};

    3.创建对象存放节点数据、邻接矩阵、输出图的方法

    class Graph{
    
        char[] data;//存放结点数据
        int[][] weight;//存放边
    
        public Graph(char[] data, int[][] weight) {
            this.data = data;
            this.weight = weight;
        }
        //输出图
        public void showGraph(){
            for (int[] link:weight){
                System.out.println(Arrays.toString(link));
            }
        }
    }

    接下来我们使用demo 完成图的创建与输出

    public static void main(String[] args) {
    
        //char[] 数组存放顶点个数
        char[] data = new char[]{'A','B','C','D','E','F','G'};
    
        //使用邻接矩阵描述权重值表示0 代表无
        int[][] weight = new int[][]{
                {0,5,7,0,0,0,0},
                {5,0,0,9,0,0,3},
                {7,0,0,0,8,0,0},
                {0,9,0,0,0,4,0},
                {0,0,8,0,0,5,4},
                {0,0,0,4,5,0,6},
                {2,3,0,0,4,6,0}
        };
        Graph graph = new Graph(data , weight);
        graph.showGraph();
    }

    图片.png

    4.接下来我们根据之前的思路,创建对应的集合思路

    class VisitedVertex{
    
        public int[] already_arr;//记录顶点是否访问过的集合
    
        public int[] pre_visited;//每个下标对应的值,作为前一个顶点的下标
    
        public int[] dis;//记录顶点到其他其他顶点的距离
    
        /**
         *
         * @param length 记录顶点的个数
         * @param index 出发顶点的下标,比如说G订单下标为:6
         */
        public VisitedVertex(int length,int index) {
            this.already_arr = new int[length];
            this.pre_visited = new int[length];
            this.dis = new int[length];
        }
    }

    根据我们的图解思路,有以下的事情需要做:

    1.出发顶点与其他顶点的距离,由于不知道,所以先初始化为最大值
    2.出发顶点需要初始化为:已访问
    3.出发顶点与自己的距离初始化为:0

    class VisitedVertex{
    
        //省略其他关键代码...
        /**
         *
         * @param length 记录顶点的个数
         * @param index 出发顶点的下标,比如说G订单下标为:6
         */
        public VisitedVertex(int length,int index) {
            this.already_arr = new int[length];
            this.pre_visited = new int[length];
            this.dis = new int[length];
            //出发顶点需要初始化为:已访问
            this.already_arr[index] =1;
            //暂时先初始化与其他顶点的距离为最大值
            Arrays.fill(dis,6535);
            //出发顶点与自己的距离初始化为:0
            this.dis[index] = 0;
        }
    }

    当我们知道某个顶点是否被访问过?怎么办?

    这时添加辅助方法:通过传入顶点下标,得到是否已被访问

    class VisitedVertex{
        
        //省略其他关键代码...
        /**
         * 功能:判断index顶点是否被访问过
         * @param index
         * @return 访问过返回true 否则false
         */
        public boolean in(int index){
            return already_arr[index] == 1;
        }
    }

    前面我们分析G顶点时:使用数组记录,并将A、B、E、F的前驱顶点指向G顶点下标

    这时我们添加辅助方法:更新某顶点的前驱节点指向index顶点

    class VisitedVertex{
        
        //省略其他关键代码...
        /**
         * 更新某顶点的前驱节点指向index下标的顶点
         * @param pre 某节点的下标
         * @param index 指向顶点的下标
         */
        public void updatePre(int pre,int index){
            pre_visited[pre] = index;
        }
    }

    当我们需要知道某顶点i,它与index顶点之间的距离是多少,怎么办?

    同时添加辅助方法:通过传入顶点下标,返回与index的距离权值

    class VisitedVertex{
        
        //省略其他关键代码...
        /**
         * 功能:返回顶点i与index 顶点的距离
         * @param i
         * @return
         */
        public int getDis(int i){
            return dis[i];
        }
    }

    前面我们分析G顶点时:使用数组记录,同时判断A、B、E、F与G顶点的连接权值

    这时我们添加辅助方法:修改i顶点与index节点的连接权值

    示例:更新A顶点与G顶点的连接权值,dis[A顶点下标] = 连接权值

    class VisitedVertex{
        
        //省略其他关键代码...
        /**
         * 功能:重新赋值i顶点与index节点的连接权值
         * @param i i顶点的下标
         * @param len 与index节点的连接权值
         */
        public void updateDis(int i,int len){
            dis[i] = len;
        }
    }

    这时我们添加辅助方法:更新遍历index顶点的所有连接节点与index的权值距离

    示例:更新A、B、E、F顶点与G顶点的连接权值,dis[顶点下标] = 连接权值

    那么我们就需要获取到index顶点的所有连接节点

    class Graph{
        //省略其他关键代码...
        /**
         * 功能:更新遍历index顶点的所有连接节点与index的权值距离
         * @param index 
         */
        private void update(int index){
            int len = 0;
            //获取到index顶点的所有连接顶点
            int[] matrix = weight[index];
            for (int j = 0; j<matrix.length;j++){
                len = weight[index][j];
                if(!vv.in(j) && len <vv.getDis(j) ){
                    vv.updatePre(j,index);
                    vv.updateDis(j,len);
                }
            }
        }
    }

    这段代码什么意思呢?我以之前的图解思路G顶点来分析一波看看

    即index = G顶点下标,我们从获取到G顶点的的所有连接节点开始

    image.png
    image.png

    此时,我们将A、B、E、F 连接节点for循环,遍历下标获取

    此时连接顶点A:对应的下标即为0,那么对应的代码是weight6

    此时连接顶点A与G顶点的连接权值就是:2,其他请看下图

    image.png

    前面提到:过出发顶点与其他顶点的距离,由于不知道,所以先初始化为最大值

    所以只要顶点A没访问过,并且与G顶点连接权值小于最大值

    那么我们就以下两件事情:

    1.调用方法:更新某顶点的前驱节点指向index顶点,A顶点前驱节点指向G顶点

    2.调用方法:修改i顶点与index节点的连接权值,原之前的最大值改为:2

    但是刚刚的代码有一个问题:如果是G顶点到C顶点是多少呢?

    image.png

    那么我们的路径就是G-C 为9,原因是 A + C ,所以我们修改代码

    class Graph{
        //省略其他关键代码...
        /**
         * 功能:更新遍历index顶点的所有连接节点与index的权值距离
         * @param index
         */
        private void update(int index){
            int len = 0;
            //获取到index顶点的所有连接顶点
            int[] matrix = weight[index];
            for (int j = 0; j<matrix.length;j++){
                len = vv.getDis(j) + weight[index][j];
                if(!vv.in(j) && len <vv.getDis(j) ){
                    vv.updatePre(j,index);
                    vv.updateDis(j,len);
                }
            }
        }
    }

    当G的所有A、B、E、F 连接节点,都重新赋值与G顶点的连接权值后

    image.png

    到这一步,我们还需要分析,选取最小权值作为新访问节点,继续遍历操作

    这时我们添加辅助方法:继续选择并返回新的访问顶点

    class VisitedVertex{
        
        //省略其他关键代码...
    
        /**
         * 功能:继续选择并返回新的访问顶点
         * @return
         */
        public int updateArr(){
            int min = 6535;
            int index = 0;
            for (int i = 0;i < already_arr.length;i++){
                if(already_arr[i] == 0 && dis[i]<min){
                    min = dis[i];
                    index = i;
                }
            }
            //同时成为新的访问顶点要标注已访问过
            already_arr[index] = 1;
            return index;
        }
    }

    三、迪杰斯特拉算法编写

    public void dsj(int index){
    
        //传入顶点的个数,与出发顶点的下标
        vv = new VisitedVertex(data.length,index);
        //更新遍历index顶点的所有连接节点与index的权值距离
        update(index);
        for (int j = 1;j < data.length ; j++){
            //选择index顶点并返回新的访问顶点
            index = vv.updateArr();
            update(index);
        }
    }

    输出方法:仅供参考(提示)

    public void showDis(){
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(data[count] + "("+i+") ");
            } else {
                System.out.println("N ");
            }
            count++;
        }
        System.out.println();
    }

    我们之前的问题是:计算出G村庄到 其它各个村庄的最短距离?

    接下来让我们使用demo 测试看看

    public static void main(String[] args) {
    
        //char[] 数组存放顶点个数
        char[] data = new char[]{'A','B','C','D','E','F','G'};
    
        int maxValue = 6535;
    
        //使用邻接矩阵描述权重值表示0 代表无
        int[][] weight = new int[][]{
                {maxValue,5,7,maxValue,maxValue,maxValue,maxValue},
                {5,maxValue,maxValue,9,maxValue,maxValue,3},
                {7,maxValue,maxValue,maxValue,8,maxValue,maxValue},
                {maxValue,9,maxValue,maxValue,maxValue,4,maxValue},
                {maxValue,maxValue,8,maxValue,maxValue,5,4},
                {maxValue,maxValue,maxValue,4,5,maxValue,6},
                {2,3,maxValue,maxValue,4,6,maxValue}
        };
        Graph graph = new Graph(data ,weight);
        //graph.showGraph();
        graph.dsj(6);
        graph.show();
    }
    
    运行结果如下:
    A(2) B(3) C(9) D(10) E(4) F(6) G(0)

    参考资料


    展开全文
  • 介绍 对于dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法,但是...就拿上图来说,假如直到的路径和长度已知,那么可以使用dijk...

    介绍

    对于dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法,但是可能不清楚其中的作用和原理,又或许,你曾经感觉它很难,那么,这个时候正适合你重新认识它。

    Dijkstra能是干啥的?
    在这里插入图片描述

    Dijkstra是用来求单源最短路径的

    就拿上图来说,假如直到的路径和长度已知,那么可以使用dijkstra算法计算南京到图中所有节点的最短距离。

    单源什么意思?

    • 从一个顶点出发,Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。

    bfs求的最短路径有什么区别?

    • bfs求的与其说是路径,不如说是次数。因为bfs他是按照队列一次一次进行加入相邻的点,而两点之间没有权值或者权值相等(代价相同)。处理的更多是偏向迷宫类的这种都是只能走邻居(不排除特例)。

    Dijkstra在处理具体实例的应用还是很多的,因为具体的问题其实带权更多一些。

    比如一个城市有多个乡镇,乡镇可能有道路,也可能没有,整个乡镇联通,如果想计算每个乡镇到a镇的最短路径,那么Dijkstra就派上了用场。

    算法分析

    对于一个算法,首先要理解它的运行流程
    对于一个Dijkstra算法而言,前提是它的前提条件和环境:

    • 一个连通图,若干节点,节点可能有数值,但是路径一定有权值。并且路径不能为负。否则Dijkstra就不适用。

    Dijkstra的核心思想是贪心算法的思想。不懂贪心?

    贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
    贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

    对于贪心算法,在很多情况都能用到。下面举几个不恰当的例子!

    打个比方,吃自助餐,目标是吃回本,那么胃有限那么每次都仅最贵的吃。

    上学时,麻麻说只能带5个苹果,你想带最多,那么选五个苹果你每次都选最大的那个五次下来你就选的最重的那个。

    不难发现上面的策略虽然没有很强的理论数学依据,或者不太好说明。但是事实规律就是那样,并且对于贪心问题大部分都需要排序,还可能会遇到类排序。并且一个物体可能有多个属性,不同问题需要按照不同属性进行排序,操作。

    那么我们的Dijkstra是如何贪心的呢?对于一个点,求图中所有点的最短路径,如果没有正确的方法胡乱想确实很难算出来,并且如果暴力匹配复杂度呈指数级上升不适合解决实际问题。

    那么我们该怎么想呢?

    Dijkstra算法的前提

    1. 首先,Dijkstra处理的是带正权值的有权图,那么,就需要一个二维数组(如果空间大用list数组)存储各个点到达()的权值大小。(邻接矩阵或者邻接表存储)
    2. 其次,还需要一个boolean数组判断那些点已经确定最短长度,那些点没有确定。int数组记录距离(在算法执行过程可能被多次更新)。
    3. 需要优先队列加入已经确定点的周围点。每次抛出确定最短路径的那个并且确定最短,直到所有点路径确定最短为止。

    简单的概括流程为

    • 一般从选定点开始抛入优先队列。(路径一般为0),boolean数组标记0的位置(最短为0) , 然后0周围连通的点抛入优先队列中(可能是node类),并把各个点的距离记录到对应数组内(如果小于就更新,大于就不动,初始第一次是无穷肯定会更新),第一次就结束了
    • 从队列中抛出距离最近的那个点B第一次就是0周围邻居)。这个点距离一定是最近的(所有权值都是正的,点的距离只能越来越长。)标记这个点为true并且将这个点的邻居加入队列(下一次确定的最短点在前面未确定和这个点邻居中产生),并更新通过B点计算各个位置的长度,如果小于则更新!
      在这里插入图片描述
    • 重复二的操作,直到所有点都确定。
      在这里插入图片描述

    算法实现

    package 图论;
    
    import java.util.ArrayDeque;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class dijkstra {
        static class node
        {
            int x; //节点编号
            int lenth;//长度
            public node(int x,int lenth) {
                this.x=x;
                this.lenth=lenth;
            }
        }
    
        public static void main(String[] args) {
             
            int[][] map = new int[6][6];//记录权值,顺便记录链接情况,可以考虑附加邻接表
            initmap(map);//初始化
            boolean bool[]=new boolean[6];//判断是否已经确定
            int len[]=new int[6];//长度
            for(int i=0;i<6;i++)
            {
                len[i]=Integer.MAX_VALUE;
            }
            Queue<node>q1=new PriorityQueue<node>(com);
            len[0]=0;//从0这个点开始
            q1.add(new node(0, 0));
            int count=0;//计算执行了几次dijkstra
            while (!q1.isEmpty()) {
                node t1=q1.poll();
                int index=t1.x;//节点编号
                int length=t1.lenth;//节点当前点距离
                bool[index]=true;//抛出的点确定
                count++;//其实执行了6次就可以确定就不需要继续执行了  这句可有可无,有了减少计算次数
                for(int i=0;i<map[index].length;i++)
                {
                    if(map[index][i]>0&&!bool[i])
                    {
                        node node=new node(i, length+map[index][i]);
                        if(len[i]>node.lenth)//需要更新节点的时候更新节点并加入队列
                        {
                            len[i]=node.lenth;
                            q1.add(node);
                        }
                    }
                }
            }       
            for(int i=0;i<6;i++)
            {
                System.out.println(len[i]);
            }
        }
        static Comparator<node>com=new Comparator<node>() {
    
            public int compare(node o1, node o2) {
                return o1.lenth-o2.lenth;
            }
        };
    
        private static void initmap(int[][] map) {
            map[0][1]=2;map[0][2]=3;map[0][3]=6;
            map[1][0]=2;map[1][4]=4;map[1][5]=6;
            map[2][0]=3;map[2][3]=2;
            map[3][0]=6;map[3][2]=2;map[3][4]=1;map[3][5]=3;
            map[4][1]=4;map[4][3]=1;
            map[5][1]=6;map[5][3]=3;    
        }
    }
    

    执行结果:
    在这里插入图片描述
    当然,dijkstra算法比较灵活,实现方式也可能有点区别,但是思想是不变的:一个贪心思路。dijkstra执行一次就能够确定一个点,所以只需要执行点的总和次数即可完成整个算法。

    展开全文
  • 迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法。本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实现在一个带权值的有向图中,选定某一个...
  • 主要思路:要求网图(非网图没有权值)中两点A(start)、N(end)的最短...这些顶点与N连通的边上的权值加上A点到这些顶点的最短路径,就是A到N的最路径。核心就是A点开始一直找相关顶点的最短路径,直到N点。 ...
  • 迪杰斯特拉算法算法思想: 设有两个顶点集合S和T,集合S存放途中已经找到最短路径的顶点,集合T存放的是途中剩余顶点。初始状态是,集合S只包含源点V0,然后不断从集合T中 选取到顶点V0的路径长度最短的顶点Vu并入...
  • 不同于二叉树,二叉树是应用在数据存储结构提高查询效率的,而图论则是用在辅助决策系统中,求得最优化解的等等,而本篇文章中介绍的floyd(弗洛伊德)算法、dijkstra(迪杰斯特拉)算法 是分别用于解决多元路径和...
  • 从一个点出发能否回到出发点 广度优先遍历 关键数据结构:队列 应用:游戏中找寻路径问题 迪杰斯特拉算法(dijkstra) 该算法主要解决最短路径问题,采用的是贪心思想 对象:权重图 核心思想:每次从路径最短的点...
  • 迪杰斯特拉关键理念:找出图中开销最低的节点,并保证没有到该节点开销更低的路径 以下面的图为例: 要解决这个问题,需要三个散列表:  graph 起点 A 6 B 2 A final 1 B A 3 ...
  • Dijkstra迪杰斯特拉算法总结 原始模板(洛谷P4779) #include<iostream> #include<cstdio> #include<algorithm> #include<cctype> #include<queue> #include<cstdlib> using ...
  • 数据结构——图——迪杰斯特拉(Dijkstra )算法 这是一个按路径长度递增的次序产生最短路径的算法。它的思路大体是这样的。 比如说要求图7-7-3中顶点v0到顶点v1的最短距离,没有比这更简单的了,答案就是1,路径就是...
  • 我感觉这个和prim还是有点相似之处的,关键这里多了一个记录上次最短路径的和p,光看代码没用,要知道思想 #include <stdio.h> #define MAX_SIZE 55 #define INF 0xFFFFFF int G[MAX_SIZE][MAX_SIZE]; int vis...
  • 官方定义:对于内网图而言,最短路径是指两顶点之间经过的边上权值之和最小的路径。 并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。 由于非内网图没有边上的权值,所谓的最短路径其实是指两顶点之间...
  • 应用:游戏中找寻路径问题 七、迪杰斯特拉算法(dijkstra) 1.该算法主要解决最短路径问题,采用的是贪心思想 2.对象:权重图 3.算法的核心思想:每次从路径最短的点出发遍历相邻边,检测改路径值(确保相邻点也是...
  • 前面我们已经了解到了无环有向图怎样求关键路径的方法,今天我们来看看无向图怎样求最短路径,这在实际应用过程中的作用很大,不如交通路线图,从出发点到终点,走哪条路用时最短,或者花费最少等问题。 我们先来看...
  • 关键:将弧按权值递增排序,按到起点路径长度的从小到大加入U。 这样做,下一条构成的路径(设终点为x),必然是v0到vx的最短路径,且必定是b2或者是B1+b2。即,v0到vx的最短路径不会是通过A1 + a2 + A3这种方法产生...
  • 关键代码 vector<int> Dijkstra(vector<vector<int>> matrix,int s) { //matrix邻接矩阵,s源点 int n = matrix.size(); //节点总数 vector<int> dis(n,INF); //distance记录最短路径...
  • //迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径p[v]及带权长度D[v] //p[][]=-1表示没有路径,p[v][i]存的是从v0到v当前求得的最短路径经过的第i+1个顶点(这是打印最短路径关键),则v0到v的最短路径即为p...
  • //希望大家可以认真学习这个算法,如果你很聪明请例外,我这么low,只有多理解了,先之后每天打一边,一个月后我才能向你保证我可以流畅的使用迪杰斯特拉了。 i,j代表接结点(就是连接点) flag【】代表...
  • 目前,单源最短路径比较好的算法有迪杰斯特拉算法(贪心算法,效率最高,局限:图中不可有负权边),贝尔曼-福特算法(可以判断能否求出最短路径并找出负权环,但速度比迪杰斯特拉算法慢)。多源最短路径有弗洛伊德...
  • 爬山法和模拟退火算法通常...而迪杰斯特拉算法虽然能够得到最短路径,但是由于需要大量的计算,比较消耗性能,因此,实际应用中并不多。关于爬山法和模拟退火算法的介绍,百度上不是很清楚,其他的一些资料上也介绍的
  • (3)迪杰斯特拉算法(dijkstra): 该算法主要解决最短路径问题,采⽤是贪⼼思想; 对象:权重图; 该算法核⼼思想是:每次从路径最短的点出发遍历相邻边,检测修改路径值(确保相邻点也是最短),从未被确认路径...
  • 迪杰斯特拉(dijkstra)算法详解

    千次阅读 2016-03-02 15:21:41
    它的关键思想是以起始点为中心,向外一层层扩散,直到扩展到终点为止。Dijkstra算法能够得出最短路径的最优解,不过它需要遍历计算的节点相当多,所以效率不高。    首先,用最通俗的语言解释。假定有3个...
  • 迪杰斯特拉算法的实现(c++)

    千次阅读 2018-12-05 20:51:24
    迪杰斯特拉算法是一种用于求解最短路径的算法,关键在于每一次循环均能确定下一个永久标号点,从而方便求解最短路径。 教程传送门:https://www.bilibili.com/video/av33533137/?p=23 按路径长度递增次序产生算法...
  • 先用迪杰斯特拉找到最短路,然后枚举最短路中的每一条路进行*2,并持续进行迪杰斯特拉算最短路,找到差距最大的。 由于点的数量比较少,导致最短路径中边的数量也比较少,因此可以枚举。 #include #include...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,061
精华内容 824
关键字:

关键路径迪杰斯特拉