迪杰斯特拉算法 订阅
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。 [1] 展开全文
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。 [1]
信息
别    称
狄克斯特拉算法 [1]
简    称
Dij算法 [1]
分    类
计算机算法 [1]
用    途
单源最短路径问题 [1]
中文名
迪克斯特拉算法 [1]
外文名
Dijkstra's Algorithm [2]
迪克斯特拉算法定义
Dijkstra算法一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 [2] 
收起全文
精华内容
下载资源
问答
  • 迪杰斯特拉算法实现;迪杰斯特拉--算法思想; 设给定源点为VsS为已求得最短路径的终点集开始时令S={Vs} 当求得第一条最短路径(Vs Vi)后S为{VsVi} 根据以下结论可求下一条最短路径 设下一条最短路径终点为Vj 则Vj只有 ...
  • 一、 迪杰斯特拉算法思想 Dijkstra算法主要针对的是有向图的单元最短路径问题,且不能出现权值为负的情况!Dijkstra算法类似于贪心算法,其应用根本在于最短路径的最优子结构性质。 最短路径的最优子结构性质: ...
  • 总结最短路径算法关键先把已知最短路径顶点集...集中在加入时可以记录每个顶点的最短路径也可以在加入完毕 后回溯找到每个顶点的最短路径和权重 迪杰斯特拉算法用于求解一个有向图也 可以是无向图无向图是有向图的一种
  • 数据结构实验 迪杰斯特拉算法
  • 数据结构与算法中图求最短路径,迪杰斯特拉算法的实现,带详细注释,可完整实现。
  • 通过邻接矩阵的数据结构存储一副图结构。利用迪杰斯特拉算法(C++实现)求其最短路径。
  • 迪杰斯特拉算法

    2018-04-06 13:42:34
    迪杰斯特拉算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以...
  • 用python实现迪杰斯特拉算法,单源最短路径,有向图权值无负值,用邻接矩阵来存储有向图,实现路径存储和路径打印
  • 由于AOE网中的某些活动能够同时进行,故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。
  • matlab编写迪杰斯特拉算法求解求最短路问题,文件是程序源代码
  • 迪杰斯特拉算法的Java实现
  • def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径,并返回该路径和代价 print(Start Dijstra Path……) path=[]#s-d的最短路径 n=len(network)#邻接矩阵维度,即节点个数 fmax=999 w=[[0 for i in ...
  • 用MATLAB实现迪杰斯特拉算法来寻找最短路径,压缩包中DIJ为算法的执行程序,SymMatrix为将邻接矩阵补齐为对称矩阵的程序,两个graph文件存储的两个邻接矩阵,DIJ加载了其中一个进行计算。也可以自己重新编辑邻接矩阵...
  • Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。...下面这篇文章就给大家介绍关于C++用Dijkstra算法(迪杰斯特拉算法)求最短路径的方法,下面来一起看看吧。
  • 用matlab解决迪杰斯特拉问题,内附相关理解论文,有助于理解
  • 一步步带你用Python实现迪杰斯特拉算法

    基本概述

    • 应用场景:
      在这里插入图片描述
      (1)分析一下,虽然还是求最短路径,但是是到各个点的最短路径,假如从G点出发,除了能直接到达的:A、B、E、F,如果要到达D点就有两种选择:一是GBD,二是GFD,选择出一条最短路径

    • 迪杰斯特拉算法介绍:
      在这里插入图片描述

    • 迪杰斯特拉算法过程:

    在这里插入图片描述
    在这里插入图片描述

    图解

    在这里插入图片描述

    Python实现

    # 迪杰斯特拉算法
    
    class VisitedVertex(object):
        def __init__(self, length: int, index: int):
            """
            :param length: 表示顶点的个数
            :param index: 出发顶点对应的下标,比如G顶点,下标就是6
            """
            self.index = index  # 传入的顶点序号,打印时需要用到
            self.ver = None  # 为了便于打印顶点封装一个对象
            
            # 记录各个顶点是否访问过 1表示访问过,0表示未访问过,会动态更新
            self.already_array = [0] * length
            # 每个下标对应的值为前一个顶点的下标,会动态更新
            self.pre_visited = [0] * length
            # 记录出发顶点到其他所有顶点的距离,比如G为出发点,就记录G到其他顶点的距离,会动态更新,求的最短距离会存放在dis
            # 初始化 dis数组
            self.dis = [float('inf')] * length
            # 设置出发顶点被访问过为1
            self.already_array[index] = 1
            # 设置出发顶点的访问距离为0
            self.dis[index] = 0
    
        def is_visited(self, index: int):
            """
            判断index顶点是否被访问过
            :param index: 传入的顶点
            :return: 如果访问过,就返回True,否则返回False
            """
            return self.already_array[index] == 1
    
        def update_dis(self, index: int, length: int):
            """
            更新出发顶点到index顶点的距离
            :param index: 传入的index
            :param length: 传入的length
            :return:
            """
            self.dis[index] = length
    
        def update_pre(self, pre: int, index: int):
            """
            更新顶点的前驱为index结点
            :param pre:
            :param index:
            :return:
            """
            self.pre_visited[pre] = index
    
        def get_dis(self, index: int):
            """
            返回出发顶点到index顶点的距离
            :param index:
            :return:
            """
            return self.dis[index]
    
        # 继续选择并返回新的访问顶点,比如这里的G完后,就是A点作为新的访问顶点(注意不是出发顶点)
        def update_arr(self):
            min_val = float('inf')
            index = 0
            for i in range(len(self.already_array)):
                if self.already_array[i] == 0 and self.dis[i] < min_val:
                    min_val = self.dis[i]
                    index = i
            # 更新 index 顶点被访问过
            self.already_array[index] = 1
            return index
    
        # 显示最后的结果,即将三个数组的情况输出
        def show_result(self):
            print('===================')
            # 输出already_array
            for item in self.already_array:
                print(item, end=' ')
            print()
            # 输出pre_visited
            for item in self.pre_visited:
                print(item, end=' ')
            print()
            # 输出dis
            for item in self.dis:
                print(item, end=' ')
            print()
            # 为了好看最后的最短距离,处理一下
            self.ver = Graph(vertex, matrix)
            count: int = 0
            for item in self.dis:
                if item != float('inf'):
                    print('{}到{}的最短距离为{}'.format(self.ver.vertex[self.index],self.ver.vertex[count],self.dis[count]))
                count += 1
            print()
    
    
    class Graph(object):
        def __init__(self, vertex: [], matrix: []):
            self.vertex = vertex  # 传入顶点数组
            self.matrix = matrix  # 传入邻接矩阵
            self.vv = None  # 已经访问顶点的集合
    
        def show_djs(self):
            self.vv.show_result()
    
        def show_graph(self):  # 显示图
            for col in self.matrix:
                print(col)
    
        # 迪杰斯特拉算法实现
        def djs(self, index: int):
            self.vv = VisitedVertex(len(self.vertex), index)
            self.update(index)  # 更新index下标顶点到周围顶点的距离和前驱结点
            for j in range(1, len(self.vertex)):
                index = self.vv.update_arr()  # 选择并返回新的访问顶点
                self.update(index)  # 更新index下标顶点到周围顶点的距离和前驱结点
    
        # 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
        def update(self, index):
            length: int = 0
            # 根据遍历邻接矩阵的 matrix[index]
            for j in range(len(self.matrix[index])):
                # length 含义:出发顶点到index顶点的距离+从index顶点到j顶点的距离的和
                length = self.vv.get_dis(index) + self.matrix[index][j]
                # 如果j顶点没有被访问过,并且length小于出发顶点到j顶点的距离,就需要更新
                if not self.vv.is_visited(j) and length < self.vv.get_dis(j):
                    self.vv.update_pre(j, index)  # 更新j顶点的前驱为index顶点
                    self.vv.update_dis(j, length)  # 更新出发顶点到j顶点的距离
    
    
    if __name__ == '__main__':
        # 顶点
        vertex: [] = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
        # 邻接矩阵
        matrix: [] = [[0 for col in range(len(vertex))] for row in range(len(vertex))]
        # 用来表示一个极大的数
        F: float = float('inf')
        matrix[0] = [F, 5, 7, F, F, F, 2]
        matrix[1] = [5, F, F, 9, F, F, 3]
        matrix[2] = [7, F, F, F, 8, F, F]
        matrix[3] = [F, 9, F, F, F, 4, F]
        matrix[4] = [F, F, 8, F, F, 5, 4]
        matrix[5] = [F, F, F, 4, 5, F, 6]
        matrix[6] = [2, 3, F, F, 4, 6, F]
        # 创建Graph对象
        g = Graph(vertex, matrix)
        g.show_graph()
        # 测试迪杰斯特拉算法
        g.djs(6)
        g.show_djs()
    ''' 输出结果
    [inf, 5, 7, inf, inf, inf, 2]
    [5, inf, inf, 9, inf, inf, 3]
    [7, inf, inf, inf, 8, inf, inf]
    [inf, 9, inf, inf, inf, 4, inf]
    [inf, inf, 8, inf, inf, 5, 4]
    [inf, inf, inf, 4, 5, inf, 6]
    [2, 3, inf, inf, 4, 6, inf]
    ===================
    1 1 1 1 1 1 1 
    6 6 0 5 6 6 0 
    2 3 9 10 4 6 0 
    G到A的最短距离为2
    G到B的最短距离为3
    G到C的最短距离为9
    G到D的最短距离为10
    G到E的最短距离为4
    G到F的最短距离为6
    G到G的最短距离为0
    '''
    
    展开全文
  • 用于求解路径规划算法,Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的...
  • 通过输入两个点,能够实现找到最短路径。源代码能运行,简单易懂
  • 迪杰斯特拉算法算法步骤: (1)初始时,S只包含源点。 (2)从U中选取一个距离v最小的顶点k加入S中(该选定的距离就是v到k的最短路径长度)。 (3)以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到...
  • C语言实现迪杰斯特拉算法,亲测好用,放在正确的环境下就可运行
  • Dijkstra算法(迪杰斯特拉算法

    万次阅读 多人点赞 2019-06-24 18:06:30
    迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的,是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。 迪杰斯特拉算法的主要特点是以起始点为中心向外层层扩展,直到扩展到终点...

    对比算法好坏需要考虑的因素

    1. 执行算法所耗费的时间
    2. 执行算法所耗费的存储空间

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

    迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的,是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。
    迪杰斯特拉算法的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

    迪杰斯特拉算法的成功率是最高的,因为它每次必能搜索到最优路径。但迪杰斯特拉算法算法的搜索速度是最慢的。迪杰斯特拉算法求一个点到其他所有点的最短路径时间复杂度为 O ( n 2 ) O(n^2) O(n2)

    基本思想

    通过迪杰斯特拉算法计算图G中的最短路径时,需要指定起点s。
    此外,需要引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
    初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是“起点s到该顶点的路径”。然后,从U中找到路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。然后,再从U中找到路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。……重复该操作,直到遍历完所有顶点。

    操作步骤

    1. 初始时, S只包含起点s;U包含除s之外的其他顶点,且U中顶点的距离为“起点s到该顶点的距离”【例如:U中顶点v的距离为(s, v)的长度,然后s和v不相邻,则v的距离为∞】。
    2. 从U中选出“距离最短的顶点k”,并将顶点k加入到S中;同时,从U中移除顶点k。
    3. 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其他顶点的距离;例如,(s, v)的距离可能大于(s, k)+(k, v)的距离。
    4. 重复步骤2和3,直到遍历完所有顶点。

    图解

    在这里插入图片描述

    ----- S是已计算出最短路径的顶点的集合
    ----- U是未计算出最短路径的顶点的集合
    ----- C(3)表示顶点C到起点D的最短距离为3

    1. 选择顶点D
      S={D(0)}
      U={A(∞), B(∞), C(3), E(4), F(∞), G(∞)}
      在这里插入图片描述
    2. 选取顶点C
      S={D(0), C(3)}
      U={A(∞), B(13), E(4), F(9), G(∞)}
      在这里插入图片描述
    3. 选取顶点E
      S={D(0), C(3), E(4)}
      U={A(∞), B(13), F(6), G(12)}
      在这里插入图片描述
    4. 选取顶点F
      S={D(0), C(3), E(4), F(6)}
      U={A(22), B(13), G(12)}
      在这里插入图片描述
    5. 选取顶点G
      S={D(0), C(3), E(4), F(6), G(12)}
      U={A(22), B(13)}
      在这里插入图片描述
    6. 选取顶点B
      S={D(0), C(3), E(4), F(6), G(12), B(13)}
      U={A(22)}
      在这里插入图片描述
    7. 选取顶点A
      S={D(0), C(3), E(4), F(6), G(12), B(13), A(22)}
      U={}
      在这里插入图片描述
    展开全文
  • 主要实现用迪杰斯特拉算法在win32控制台程序下编写的校园导航系统。
  • 可以用迪杰斯特拉算法求解。 dijkstra算法求最短距离 算法思路: 该算法使用了三个辅助数组,首先应理解它们的含义: visited[]:保存各顶点是否被访问过,初始时,除了其实顶点为true外,其余都是false。 .

     算法背景:

    图中的A,B,C,D,E,F,G,代表7个村庄,边上的权值带表两村庄之间的距离,现在要从某一个村庄,例如G村庄,往另外几个村庄送邮件,问G村庄到其他各村庄的最短距离分别是多少?

    思路:

    该问题实际是求从某一顶点到其余顶点的最短距离,即单源点到其余顶点的距离。可以用迪杰斯特拉算法求解。

    dijkstra算法求最短距离

    算法思路:

    该算法使用了三个辅助数组,首先应理解它们的含义:

    • visited[]:保存各顶点是否被访问过,初始时,除了其实顶点为true外,其余都是false。
    • distance[]:存放动态的单源点到其余点的最短距离,初始时为单源点到各店的距离,其中单源点自身距离设置为0。
    • prePath[]:保存当前结点的前驱结点,方便最后找最短距离的路径,初始时除与单源点有直接路径的顶点设置为单源点索引外其余都设置为-1,即没有前驱点。

     该算法将图中顶点分为两类:已访问过的和没访问过的,这里的已访问过是指对应顶点的distance中的距离已经是真实的最短的距离了,通过visited中的true和false实现。初始时,只有起始顶点为true,然后在false的顶点中找出动态距离最短的顶点(体现贪心思想),将其置为true,此时访问该点的邻接边,并对比“过渡距离”是否小于distance中的距离,小于则更新distance和prePath。依次循环直到都置为true为止。

     核心代码:

    算法分析:

    该算法用了两层for,外层为需要访问的顶点个数,时间复杂度为O(n),内层有两个for,第一个for为挑选未被访问的顶点的最短距离,时间复杂度为O(n),第二个for为在与选中顶点有直接路径的顶点中对比距离是否需要更新,时间复杂度为O(n),所以总的时间复杂度为O(n²)。

    dijkstra算法可通过改变存储结构(邻接表)和存储距离(优先队列)的方式做优化,使最后复杂度为O(nlogn)。

    具体见:迪杰斯特拉算法优化(dijkstra)icon-default.png?t=L9C2https://blog.csdn.net/weixin_48898946/article/details/121004513

    public void dijkstra(int index) {
    	for(int i = 0; i < numOfVertex;i++) {//初始化各辅助数组
    		distant[i] = edge[index][i];
    		if(edge[index][i] != INF) {
    			prePath[i] = index;
    		}else {
    			prePath[i] = -1;
    		}
    	}
    	visit[index] = true;//置初始起点已访问
    	for(int i = 0; i < numOfVertex - 1;i++) {
    		int des = 0;
    		int minDis = INF;
    		for(int j = 0; j < numOfVertex ;j++) {//挑选为被访问的最短距离的顶点
    			if(visit[j] == false && minDis > distant[j]) {
    				minDis = distant[j];
    				des = j;
    			}
    		}
    		visit[des] = true;//更新为已访问
    		
    		for(int j = 0; j < numOfVertex;j++) {//对比更新最短距离
    			int len = edge[des][j] + distant[des];
    			if(len < distant[j] && len < INF) {
    				distant[j] = len;
    				prePath[j] = des;
    			}
    		}
    	}
    	System.out.printf("顶点%c到其余各点的最短距离:\n",vertex[index]);
    	for (int i = 0; i < numOfVertex; i++) {
    		if (i != index) {
    			System.out.printf("顶点%c到顶点%c的最短距离是%d\n", vertex[index], vertex[i], distant[i]);
    		}
    	}
    	System.out.println();
    }

    java代码:

    import java.util.*;
    
    public class Dijkstra {
    	public static void main(String[] args) {
    		final int INF = 0x3f3f3f3f;
    		char[]vertex = {'A','B','C','D','E','F','G'};
    		int [][]edge = new int [][] {
    			{INF,5,7,INF,INF,INF,2},
    			{5,INF,INF,9,INF,INF,3},
    			{7,INF,INF,INF,8,INF,INF},
    			{INF,9,INF,INF,INF,4,INF},
    			{INF,INF,8,INF,INF,5,4},
    			{INF,INF,INF,4,5,INF,6},
    			{2,3,INF,INF,4,6,INF}
    		};
    		Graph graph = new Graph(vertex, edge);
    		graph.printGraph();
    		System.out.println("\n初始起点为G点:\n");
    		graph.dijkstra(6);
    		graph.printPath(6);
    	}
    }
    class Graph{
    	final int INF = 0x3f3f3f3f;//设置一个“大数”
    	char []vertex;//顶点数组
    	int [][]edge;//邻接矩阵
    	int numOfVertex;//顶点个数
    	boolean []visit;//访问标志数组
    	int []distant;//最短距离数组
    	int []prePath;//最短路径前驱数组
    	
    	public Graph(char[] vertex, int[][] edge) {
    		this.vertex = vertex;
    		this.edge = edge;
    		numOfVertex = vertex.length;
    		visit = new boolean[numOfVertex];
    		distant = new int [numOfVertex];
    		prePath = new int [numOfVertex];
    	}
    	
    	public void printGraph() {
    		System.out.println("邻接矩阵为:");
    		for(int[] data : edge) {
    			System.out.println(Arrays.toString(data));
    		}
    	}
    	
    	public void dijkstra(int index) {
    		for(int i = 0; i < numOfVertex;i++) {//初始化各辅助数组
    			distant[i] = edge[index][i];
    			if(edge[index][i] != INF) {
    				prePath[i] = index;
    			}else {
    				prePath[i] = -1;
    			}
    		}
    		visit[index] = true;//置初始起点已访问
    		
    		for(int i = 0; i < numOfVertex - 1;i++) {
    			int des = 0;
    			int minDis = INF;
    			for(int j = 0; j < numOfVertex ;j++) {//挑选为被访问的最短距离的顶点
    				if(visit[j] == false && minDis > distant[j]) {
    					minDis = distant[j];
    					des = j;
    				}
    			}
    			visit[des] = true;//更新为已访问
    			
    			for(int j = 0; j < numOfVertex;j++) {//对比更新最短距离
    				int len = edge[des][j] + distant[des];
    				if(len < distant[j] && len < INF) {
    					distant[j] = len;
    					prePath[j] = des;
    				}
    			}
    		}
    		System.out.printf("顶点%c到其余各点的最短距离:\n",vertex[index]);
    		for (int i = 0; i < numOfVertex; i++) {
    			if (i != index) {
    				System.out.printf("顶点%c到顶点%c的最短距离是%d\n", vertex[index], vertex[i], distant[i]);
    			}
    		}
    		System.out.println();
    	}
    	
    	public void printPath(int m) {
    		for(int i = 0; i < numOfVertex;i++) {
    			if(i == m) continue;
    			int []flag = new int[numOfVertex];
    			int index = 0;
    			flag[index++] = i;
    			int k = i;
    			while(true) {
    				k = prePath[k];
    				if(k == m || k == -1)break;
    				flag[index++] = k;
    			}
    			flag[index] = m;
    			System.out.printf("顶点%c到顶点%c的最短路径为:",vertex[m],vertex[i]);
    			for(int j = index; j >= 0; j--) {
    				System.out.print(vertex[flag[j]] + " ");
    			}
    			System.out.println();
    		}
    	}
    }

    程序输出:

    邻接矩阵为:
    [1061109567, 5, 7, 1061109567, 1061109567, 1061109567, 2]
    [5, 1061109567, 1061109567, 9, 1061109567, 1061109567, 3]
    [7, 1061109567, 1061109567, 1061109567, 8, 1061109567, 1061109567]
    [1061109567, 9, 1061109567, 1061109567, 1061109567, 4, 1061109567]
    [1061109567, 1061109567, 8, 1061109567, 1061109567, 5, 4]
    [1061109567, 1061109567, 1061109567, 4, 5, 1061109567, 6]
    [2, 3, 1061109567, 1061109567, 4, 6, 1061109567]
    
    初始起点为G点:
    
    顶点G到其余各点的最短距离:
    顶点G到顶点A的最短距离是2
    顶点G到顶点B的最短距离是3
    顶点G到顶点C的最短距离是9
    顶点G到顶点D的最短距离是10
    顶点G到顶点E的最短距离是4
    顶点G到顶点F的最短距离是6
    
    顶点G到顶点A的最短路径为:G A 
    顶点G到顶点B的最短路径为:G B 
    顶点G到顶点C的最短路径为:G A C 
    顶点G到顶点D的最短路径为:G F D 
    顶点G到顶点E的最短路径为:G E 
    顶点G到顶点F的最短路径为:G F 
    

    展开全文
  • 基于matlab的迪杰斯特拉算法,可用于解决最短路问题的解决
  • 有机器人详细迪的杰斯特拉算法和如何避开障碍物的介绍,对于新手来说值得一看。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,728
精华内容 5,091
关键字:

迪杰斯特拉算法

友情链接: javaComparerUI.rar