精华内容
下载资源
问答
  • Dijkstra也叫迪杰斯特拉,是典型最短路径算法,计算一个起始节点到路径中其他所有节点的最短路径的算法和思想。在一些专业课程中如数据结构,图论,运筹学等都有介绍。其思想是一种基础的求最短路径的算法,通过基础...

    Dijkstra也叫迪杰斯特拉,是典型最短路径算法,计算一个起始节点到路径中其他所有节点的最短路径的算法和思想。在一些专业课程中如数据结构,图论,运筹学等都有介绍。其思想是一种基础的求最短路径的算法,通过基础思想的变化可以解决很多复杂问题,如导航线路,动态规划等。

    Dijkstra 算法思想介绍

    如下图是一个多节点,多路径图。下面以该图为例子讲解dijkstra算法寻找最短路径的过程。

    以A点为起始点,求A点到其他点 B C D E F 5个点的最短路径,最后得出A到其他点的最短路径。

    因为要求A到其他5个点的最短距离,所以构造一个数组记录A到B C D E F 5个点的路径距离。约定:

    如果A能够直接达到节点,则使用路径长度即权值作为其距离

    如果A节点不能直接达到节点则使用无穷大表示A到该点距离。

    任何点到自身都为0

    那么在最开始时,A点到图中所有点的距离数组如下:

    A

    B

    C

    D

    E

    F

    0

    10

    无穷大

    4

    无穷大

    无穷大

    dijkstra的算法思想是从以上最短距离数组中每次选择一个最近的点,将其作为下一个点,然后重新计算从起始点经过该点到其他所有点的距离,更新最短距离数据。已经选取过的点就是确定了最短路径的点,不再参与下一次计算。

    可能看到这里你完全不明白dijkstra算法的思想,心里可能想:这是说的人话吗?不要紧,如果算法一句话就能解释清楚,那就不会出现那么多算法书了。下面我们就从实际的选取过程中理解这个思想的精髓。

    第一次选取

    构建好的数组是这样的:

    A

    B

    C

    D

    E

    F

    0

    10

    无穷大

    4

    无穷大

    无穷大

    第一步选取该最短路径数组中值最小的一个点。因为A点到本身不需要参与运算,所以从剩下的点中选择最短的一个是D。

    第二步以A-D的距离为最近距离更新A点到所有点的距离。即相当于A点经过D点,计算A到其他点的距离。

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-C:19

    A-D : A-D:4

    A-E : A-D-E:10

    A-F : A-D-F:去穷大

    A

    B

    C

    D

    E

    F

    0

    6

    19

    4

    10

    无穷大

    将现在A到各个点的距离和之前的比较,到相同点取最小值。更新了B C E的距离,得到如下新的最短距离数组:

    A

    B

    C

    D

    E

    F

    0

    6

    19

    4

    10

    无穷大

    同时现在A D两点已经计算过,不参与下面的计算。

    第二次选取

    第二次选取的数组为第一次中更新过最短距离的数组

    A

    B

    C

    D

    E

    F

    0

    6

    19

    4

    10

    无穷大

    第一步:因为A D 不参与选取,所有从剩下的点中选取最近距离是点B

    第二步:以B为最新点,更新最短数组

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-B-C:14

    A-D : A-D:4

    A-E : A-D-B-E:12

    A-F : A-D-B-F:无穷大

    A

    B

    C

    D

    E

    F

    0

    6

    14

    4

    12

    无穷大

    对比现在的最短距离和上一个数组的距离,到相同节点取最小的,C点由19更新成14,E点走A-D-E为10,距离更短所以不更新(敲黑板,这个重要),得到如下数组:

    A

    B

    C

    D

    E

    F

    0

    6

    14

    4

    10

    无穷大

    此时B点加入最短路径范围中。

    第三次选取

    上一步得到的数组为:

    A

    B

    C

    D

    E

    F

    0

    6

    14

    4

    10

    无穷大

    第一步:选取除了A B D节点之外的剩余节点中最短节点,为点E

    第二步:以E点为最新节点,更新最短路径数组

    因为在上一部中计算达到E点的距离时没有更新距离,A-D-E 为10 最短,所以更新E点到B C F点的距离时走的路径是A-D-E。注意这里的最短距离有对应的路径,选择最小值就是选择最短距离。

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-E-C:11

    A-D : A-D:4

    A-E : A-D-E:10

    A-F : A-D-E-F:22

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    22

    对比现在的最短距离和上一个数组的距离,到相同节点取最小的,更新C点走A-D-E-C 为11,比之前的A-D-B-C14距离更近,更新到F点距离,得到如下数组:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    22

    此时E点加入最短路径范围中。

    第四次选取

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    22

    第一步:选取除了A B D E节点之外的剩余节点中最短节点,为点C

    第二步:以C点为最新节点,更新最短路径数组

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-E-C:11

    A-D : 4

    A-E : A-D-E:10

    A-F : A-D-E-C-F:16

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    对比现在的最短距离和上一个数组的距离,到相同节点取最小的,更新到F点距离,可以得到如下数组:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    第五次选取

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    第一步:选取除了A B C D E节点之外的剩余节点中最短节点,也就是最后一个节点:F

    第二步:以F点为最新节点,更新最短路径数组。由于F点是最后一个点,所以也不用更新数组,目前的数组就是所求数组

    将F点加入最短路径范围中,此时所有的点都加入了最短路径范围,也就是说A点到所有点的距离都找到了。最总得出的距离值为:

    最终得到的结果为:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    最终结果

    相应的A点到所有点的最短路径走法最终得到的结果为:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    A-A:0

    A-B : A-D-B:6

    A-C : A-D-E-C:11

    A-D:4

    A-E:A-D-E:10

    A-F:A-D-E-C-F:16

    算法总结

    Dijkstra算法作为求最短路径的经典算法,个人理解为算法提供了一种思想,每走一步都是找到最短的路径,并且每走一步都实时更新所有距离,保证每次都选择最短路径。

    python实现Dijkstra

    将以上的过程使用python来实现。

    首先总结一个Dijkstra算法的核心思想,分成两步走:

    构造一个最短路径数组,每次找到数组中未访问的节点里最小的点

    以上一步的节点为最新节点,更新起始点到所有点的距离

    使用python就是实现这两步即可

    数据准备

    二维矩阵

    如何描述一个图呢?通常有两种方式,分别是:十字链表和二维矩阵。因为二维矩阵更加直观,所以选择二维矩阵。

    将上面的图描述成一个二维矩阵

    无穷大使用MAX = float('inf')表示,该数值是python中表示无穷大的一个值。

    这个二维矩阵真正直观之处在哪里呢?是能够看到任意一个点到其他点的距离。如想看D点到其他点的距离,就是:

    在我们的算法两步走中第二步要更新A点经过某点到其他点的距离,正是使用了这个特征。

    MAX= float('inf')

    matrix = [

    [0,10,MAX,4,MAX,MAX],

    [10,0,8,2,6,MAX],

    [MAX,8,10,15,1,5],

    [4,2,15,0,6,MAX],

    [MAX,6,1,6,0,12],

    [MAX,MAX,5,MAX,12,0]

    ]

    最短路径数组

    在上面讲解算法过程中有一个重要的的最短路径数组,不断更新该数组直到所有的点都被访问到。使用python语言,构造该数组:

    distance = [MAX] * len(matrix)

    len(matrix) 实际上算出的图的点的个数。初始化时所有的节点都是不可达。

    在算法过程中还有一个重要的数组,并没有体现出来,但是在python计算时也很重要,那就是访问过的点。每一次访问之后就要将访问过的点加入到该数组中,这样做是为了避免重复访问。

    used_node = [False] * len(matrix)

    初始化时认为所有点都没有访问到

    代码实现

    MAX= float('inf')

    matrix = [

    [0,10,MAX,4,MAX,MAX],

    [10,0,8,2,6,MAX],

    [MAX,8,10,15,1,5],

    [4,2,15,0,6,MAX],

    [MAX,6,1,6,0,12],

    [MAX,MAX,5,MAX,12,0]

    ]

    def dijkstra(matrix, start_node):

    #矩阵一维数组的长度,即节点的个数

    matrix_length = len(matrix)

    #访问过的节点数组

    used_node = [False] * matrix_length

    #最短路径距离数组

    distance = [MAX] * matrix_length

    #初始化,将起始节点的最短路径修改成0

    distance[start_node] = 0

    #将访问节点中未访问的个数作为循环值,其实也可以用个点长度代替。

    while used_node.count(False):

    min_value = float('inf')

    min_value_index = 999

    #在最短路径节点中找到最小值,已经访问过的不在参与循环。

    #得到最小值下标,每循环一次肯定有一个最小值

    for index in range(matrix_length):

    if not used_node[index] and distance[index] < min_value:

    min_value = distance[index]

    min_value_index = index

    #将访问节点数组对应的值修改成True,标志其已经访问过了

    used_node[min_value_index] = True

    #更新distance数组。

    #以B点为例:distance[x] 起始点达到B点的距离,

    #distance[min_value_index] + matrix[min_value_index][index] 是起始点经过某点达到B点的距离,比较两个值,取较小的那个。

    for index in range(matrix_length):

    distance[index] = min(distance[index], distance[min_value_index] + matrix[min_value_index][index])

    return distance

    start_node = int(input('请输入起始节点:'))

    result = dijkstra(matrix,start_node)

    print('起始节点到其他点距离:%s' % result)

    结果:

    请输入起始节点:0

    起始节点到其他点距离:[0, 6, 11, 4, 10, 16]

    简单总结

    学习python实现Dijkstra重要的地方有几点:

    数据构造 二维矩阵表示图

    图的访问方式 更新最短路径数组的过程无非就是分别比较二维矩阵数组中某一行的值和最短路径数组的值

    熟悉这样的处理方式,再有类似的算法也能找到解决的思路。例如一个二维矩阵,从起始点开始只能走向下的相邻的元素,求达到某点的最短路径。

    希望通过该篇文章,能够深刻理解Dijkstra算法,做到心中有数,手中有活。

    展开全文
  • #include #include #include void shortestpath( const std::vector >& paths, int from, ... std::cout 最近路径结果为:" ; for(size_t i = 0; i != path.size(); ++i){ std::cout [i] ; } std::cout ; return 0; }

    #include

    #include

    #include

    void shortestpath( const std::vector <:vector short> >& paths, int from, std::vector< short>& path){

    std:: vector flags(paths.size(), false);

    std:: vector distance(paths.size(), 0);

    path.resize(paths.size(), 0);

    for(size_t i = 0; i != paths.size(); ++i){

    distance[i] = paths[from][i];

    }

    flags[from] = 1;

    int min, pos;

    for(size_t i = 1; i != paths.size(); ++i){

    pos = -1;

    min = std:: numeric_limits::max();

    for(size_t j = 0; j != paths.size(); ++j){

    if(!flags[j] && distance[j] < min){

    min = distance[j];

    pos = j;

    }

    }

    if(pos == -1)

    break;

    flags[pos] = true;

    for(size_t j = 0; j != paths.size(); ++j){

    if(!flags[j] && paths[pos][j] != 0

    && paths[pos][j] < std::numeric_limits :: max()

    && min+paths[pos][j] < distance[j]){

    distance[j] = min + paths[pos][j];

    path[j] = pos;

    }

    }

    }

    for(size_t i = 0; i != distance.size(); ++i){

    std::cout << distance[i] << " " << std::flush;

    }

    std::cout << std:: endl;

    }

    int main(){

    std::cout << "请输入顶点数:" << std::flush;

    int sum; std::cin >> sum;

    std:: vector<:vector> > paths;

    for(int i = 0; i != sum; ++i){

    paths.push_back(std:: vector(sum, std::numeric_limits< short>::max()));

    paths[i][i] = 0;

    }

    std::cout << "请输入边数:" << std::flush;

    std::cin >> sum;

    int vi, vj, weight;

    for(int i = 0; i != sum; ++i){

    std::cin >> vi >> vj >> weight;

    paths[vi][vj] = weight;

    paths[vj][vi] = weight;

    }

    std:: vector path;

    shortestpath(paths, 0, path);

    std::cout << "最近路径结果为:" << std::flush;

    for(size_t i = 0; i != path.size(); ++i){

    std::cout << path[i] << " " << std::flush;

    }

    std::cout << std:: endl;

    return 0;

    }

    展开全文
  • 首先是核心的Dijkstra类:class="java" name="code">package mx.dijkstra;import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Stack;/*** ...

    首先是核心的Dijkstra类:

    class="java" name="code">package mx.dijkstra;

    import java.util.ArrayList;

    import java.util.HashMap;

    import java.util.Iterator;

    import java.util.Map;

    import java.util.Stack;

    /**

    * 基于 Dijkstra 贪心算法的最短路径寻找 先初始化 init 初始化一次 只可以调用一次 dijkatra方法.再次调用请重新初始化

    * @author Dewey

    */

    public class Dijkstra {

    /**

    * 点的键值集合,标识从起点到每个点的权重总和

    */

    private Map pointKeys = new HashMap();

    /**

    * 边集合,两个点成一条边.用来表示那些点可以连通和所需的权重.

    */

    private ArrayList edges = new ArrayList();

    /**

    * 从起点到每个点的最短路径集合,当算法执行完毕时,里面保存着从起点到各个点的最短路径

    */

    private Map paths = new HashMap();

    /**

    * 表示无穷大的常量

    */

    private static final int INFINITY = 99999;

    /**

    * 清空所有集合

    */

    private void reset() {

    pointKeys.clear();

    edges.clear();

    paths.clear();

    }

    /**

    * 初始化

    *

    * @param source 点的集合

    * @param edegs 边的集合

    * @param start 寻径的起点

    */

    private void init(ArrayList source, ArrayList edegs, Point start) {

    reset();

    this.edges = edegs;

    for (int i = 0; i < source.size(); i++) {// 取出每个点

    Point v = source.get(i);

    // 把每个点放入键值集合

    if (v.equals(start)) {// 当前点为起点

    // 起点到起点的键值为0

    pointKeys.put(v, 0);

    } else {

    // 到其他点为无穷大

    pointKeys.put(v, INFINITY);

    }

    // 初始化从起点到起点的路径

    Dist dist = new Dist();

    dist.setPoint(start);// 路程点为起点

    dist.setPreDist(null);// 前一个点为null

    dist.setWeight(0);// 路程开销为0

    paths.put(start, dist);// 放入路径集合

    }

    }

    /**

    * dijkstra 算法实现

    * @param source 点

    * @param edegs 边

    * @param start 寻径的起点

    * @param end 需要寻的终点

    * @return

    */

    public Stack dijkstra(ArrayList source, ArrayList edegs, Point start, Point end) {

    init(source, edegs, start);

    Integer endPointKey = null;// 从当前点走向下一个点 下一个点原来所需要的开销

    while (pointKeys.size() > 0) {// 键值集合所存在的点大于0

    Point minkeyPoint = getMinKey(pointKeys);// 获得当前键值几个拥有最小键值(开销)的点 称为当前点

    int keyValue = pointKeys.get(minkeyPoint);// 获得拥有最小键值点的键值

    ArrayList adjacentEdegs = getEdegs(edges, minkeyPoint);// 寻找与这个点相邻的边

    for (Edge edge : adjacentEdegs) {// 遍历相邻的边

    int currentKey = keyValue + edge.getWeight();// 从起点到当前点的开销 + 通过这条边到下一个点的开销 称为当前开销

    endPointKey = pointKeys.get(edge.getEnd());// 获取从起点到当前边对面点的开销

    if (endPointKey == null) {// 若获取不到 则说明对面的点已经不存在于键值集合 通常是个环路

    continue;// 可能是个环路 或 不可达

    }

    updatePath(endPointKey, edge, currentKey);// 更新路径

    }

    pointKeys.remove(minkeyPoint);

    }

    return getPaths(end);

    }

    /**

    * 更新路径

    * @param endPointKey

    * @param edge

    * @param currentKey

    */

    private void updatePath(Integer endPointKey, Edge edge, int currentKey) {

    Dist advance = null;// 每次寻径所走的路线 单步

    if (currentKey < endPointKey) {// 若当前开销 小于 原来从起点到边对面点的开销 则更新对点的键值

    pointKeys.put(edge.getEnd(), currentKey);// 覆盖原来的键值

    advance = new Dist();// 创建新的路程

    advance.setPoint(edge.getEnd());// 起点为 对面边的点

    advance.setPreDist(paths.get(edge.getStart()));// 前一个点为当前点

    advance.setWeight(edge.getWeight());// 路程长度为边的权重

    paths.put(edge.getEnd(), advance);// 放入路径集合

    }

    }

    /**

    * 算法执行完毕后 寻找重点为参数点的路径 返回路径点的栈 因为终点会被最后找到,所以返回一个栈

    * 而不是数组,这样遍历比较方便.直接执行初战操作就可以得到正确的从起点到终点所需要的点

    * @param end

    * @return

    */

    private Stack getPaths(Point end) {

    Stack stack = null;

    Iterator iterator = paths.keySet().iterator();

    while (iterator.hasNext()) {

    stack = new Stack();

    Point c = iterator.next();

    if (!c.equals(end)) {

    continue;

    }

    Dist td = paths.get(c);

    while (td != null) {

    stack.push(td.getPoint());

    td = td.getPreDist();

    }

    break;

    }

    return stack;

    }

    /**

    * 在集合中寻找值最小的元素

    * @param pointKeys

    * @return

    */

    private Point getMinKey(Map pointKeys) {

    Iterator iterator = pointKeys.keySet().iterator();

    int minValue = INFINITY;

    Point minKeyPoint = null;

    while (iterator.hasNext()) {

    Point point = iterator.next();

    Integer value = pointKeys.get(point);

    if (value < minValue) {

    minValue = value;

    minKeyPoint = point;

    }

    }

    return minKeyPoint;

    }

    /**

    * 寻找与参数点相邻的边

    * @param edges

    * @param point

    * @return

    */

    private ArrayList getEdegs(ArrayList edges, Point point) {

    ArrayList tempEdges = new ArrayList();

    for (Edge edge : edges) {

    if (edge.getStart().equals(point)) {

    tempEdges.add(edge);

    }

    }

    return tempEdges;

    }

    }

    最基本的:点的类,只是为了在寻径的时候在内存中标示一个点就可以了,如果需要属性,可以自行添加.在算法中不需要.

    package mx.dijkstra;

    /**

    * 点

    * @author Dewey

    */

    public class Point {

    }

    ?

    边的类,两条点组成一条边,并且边有权重(可以是长度),用来标示点与点之间的可连通关系,有向图的连通性就依赖这个类.

    package mx.dijkstra;

    /**

    * 点与点组成的边

    * @author Dewey

    *

    */

    public class Edge {

    /**

    * 起点

    */

    private Point start;

    /**

    * 结束点

    */

    private Point end;

    /**

    * 权重

    */

    private int weight;

    public Edge(Point start,Point end,int weight){

    this.start=start;

    this.end=end;

    this.weight=weight;

    }

    public Point getStart() {

    return start;

    }

    public void setStart(Point start) {

    this.start = start;

    }

    public Point getEnd() {

    return end;

    }

    public void setEnd(Point end) {

    this.end = end;

    }

    public int getWeight() {

    return weight;

    }

    public void setWeight(int weight) {

    this.weight = weight;

    }

    }

    ??

    路程类,标示算法每一步的前进所需要的两个点.

    package mx.dijkstra;

    /**

    * 路程

    * @author Dewey

    */

    public class Dist{

    /**

    * 路程的开销

    */

    private int weight;

    /**

    * 路程点

    */

    private Point point;

    /**

    * 前一个点

    */

    private Dist preDist;

    public int getWeight() {

    return weight;

    }

    public void setWeight(int weight) {

    this.weight = weight;

    }

    public Point getPoint() {

    return point;

    }

    public void setPoint(Point point) {

    this.point = point;

    }

    public Dist getPreDist() {

    return preDist;

    }

    public void setPreDist(Dist preDist) {

    this.preDist = preDist;

    }

    }

    ?

    一个小例子:

    public void demo1() {

    //声明点

    Point A = new MPoint(1,0,0);//id,x坐标,y坐标

    Point B = new MyPoint(2,0,0);

    Point C = new MyPoint(3,0,0);

    Point D = new MyPoint(4,0,0);

    Point E = new MyPoint(5,0,0);

    //放入点集合

    ArrayList source = new ArrayList();

    source.add(A);

    source.add(B);

    source.add(C);

    source.add(D);

    source.add(E);

    //声明边

    ArrayList edges = new ArrayList();

    edges.add(new Edge(A, B, 10));

    edges.add(new Edge(A, C, 5));

    edges.add(new Edge(B, C, 2));

    edges.add(new Edge(B, D, 1));

    edges.add(new Edge(C, B, 3));

    edges.add(new Edge(C, D, 9));

    edges.add(new Edge(C, E, 2));

    edges.add(new Edge(D, E, 4));

    edges.add(new Edge(E, D, 6));

    edges.add(new Edge(E, A, 7));

    Dijkstra d = new Dijkstra();

    Stack points = d.dijkstra(source, edges, A, D);//提供 点的集合 边的集合 起点 终点 开始寻径

    while (points.size() > 0) {

    Point p = points.pop();

    System.out.print(((MyPoint)p).getId()+">");//打印

    }

    }

    ?

    ?

    Java-Dijkstra-master.zip (1.5 MB)

    下载次数: 0

    展开全文
  • 标签:需要a算法实现三次相同个数选择动态规划infDijkstra也叫迪杰斯特拉,是典型最短路径算法,计算一个起始节点到路径中其他所有节点的最短路径的算法和思想。在一些专业课程中如数据结构,图论,运筹学等都有介绍...

    标签:需要   a算法   实现   三次   相同   个数   选择   动态规划   inf

    Dijkstra也叫迪杰斯特拉,是典型最短路径算法,计算一个起始节点到路径中其他所有节点的最短路径的算法和思想。在一些专业课程中如数据结构,图论,运筹学等都有介绍。其思想是一种基础的求最短路径的算法,通过基础思想的变化可以解决很多复杂问题,如导航线路,动态规划等。

    1|0Dijkstra 算法思想介绍

    如下图是一个多节点,多路径图。下面以该图为例子讲解dijkstra算法寻找最短路径的过程。

    20200602131316664645.png

    以A点为起始点,求A点到其他点 B C D E F 5个点的最短路径,最后得出A到其他点的最短路径。

    因为要求A到其他5个点的最短距离,所以构造一个数组记录A到B C D E F 5个点的路径距离。约定:

    如果A能够直接达到节点,则使用路径长度即权值作为其距离

    如果A节点不能直接达到节点则使用无穷大表示A到该点距离。

    任何点到自身都为0

    那么在最开始时,A点到图中所有点的距离数组如下:

    A

    B

    C

    D

    E

    F

    0

    10

    无穷大

    4

    无穷大

    无穷大

    dijkstra的算法思想是从以上最短距离数组中每次选择一个最近的点,将其作为下一个点,然后重新计算从起始点经过该点到其他所有点的距离,更新最短距离数据。已经选取过的点就是确定了最短路径的点,不再参与下一次计算。

    20200602131316898029.gif

    可能看到这里你完全不明白dijkstra算法的思想,心里可能想:这是说的人话吗?不要紧,如果算法一句话就能解释清楚,那就不会出现那么多算法书了。下面我们就从实际的选取过程中理解这个思想的精髓。

    1|1第一次选取

    构建好的数组是这样的:

    A

    B

    C

    D

    E

    F

    0

    10

    无穷大

    4

    无穷大

    无穷大

    第一步选取该最短路径数组中值最小的一个点。因为A点到本身不需要参与运算,所以从剩下的点中选择最短的一个是D。

    第二步以A-D的距离为最近距离更新A点到所有点的距离。即相当于A点经过D点,计算A到其他点的距离。

    20200602131316957595.png

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-C:19

    A-D : A-D:4

    A-E : A-D-E:10

    A-F : A-D-F:去穷大

    A

    B

    C

    D

    E

    F

    0

    6

    19

    4

    10

    无穷大

    将现在A到各个点的距离和之前的比较,到相同点取最小值。更新了B C E的距离,得到如下新的最短距离数组:

    A

    B

    C

    D

    E

    F

    0

    6

    19

    4

    10

    无穷大

    同时现在A D两点已经计算过,不参与下面的计算。

    1|2第二次选取

    第二次选取的数组为第一次中更新过最短距离的数组

    A

    B

    C

    D

    E

    F

    0

    6

    19

    4

    10

    无穷大

    第一步:因为A D 不参与选取,所有从剩下的点中选取最近距离是点B

    第二步:以B为最新点,更新最短数组

    20200602131317066963.png

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-B-C:14

    A-D : A-D:4

    A-E : A-D-B-E:12

    A-F : A-D-B-F:无穷大

    A

    B

    C

    D

    E

    F

    0

    6

    14

    4

    12

    无穷大

    对比现在的最短距离和上一个数组的距离,到相同节点取最小的,C点由19更新成14,E点走A-D-E为10,距离更短所以不更新(敲黑板,这个重要),得到如下数组:

    A

    B

    C

    D

    E

    F

    0

    6

    14

    4

    10

    无穷大

    此时B点加入最短路径范围中。

    1|3第三次选取

    上一步得到的数组为:

    A

    B

    C

    D

    E

    F

    0

    6

    14

    4

    10

    无穷大

    第一步:选取除了A B D节点之外的剩余节点中最短节点,为点E

    第二步:以E点为最新节点,更新最短路径数组

    20200602131317150942.png

    因为在上一部中计算达到E点的距离时没有更新距离,A-D-E 为10 最短,所以更新E点到B C F点的距离时走的路径是A-D-E。注意这里的最短距离有对应的路径,选择最小值就是选择最短距离。

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-E-C:11

    A-D : A-D:4

    A-E : A-D-E:10

    A-F : A-D-E-F:22

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    22

    对比现在的最短距离和上一个数组的距离,到相同节点取最小的,更新C点走A-D-E-C 为11,比之前的A-D-B-C14距离更近,更新到F点距离,得到如下数组:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    22

    此时E点加入最短路径范围中。

    1|4第四次选取

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    22

    第一步:选取除了A B D E节点之外的剩余节点中最短节点,为点C

    第二步:以C点为最新节点,更新最短路径数组

    20200602131317251522.png

    A-A : 0

    A-B : A-D-B:6

    A-C : A-D-E-C:11

    A-D : 4

    A-E : A-D-E:10

    A-F : A-D-E-C-F:16

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    对比现在的最短距离和上一个数组的距离,到相同节点取最小的,更新到F点距离,可以得到如下数组:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    1|5第五次选取

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    第一步:选取除了A B C D E节点之外的剩余节点中最短节点,也就是最后一个节点:F

    第二步:以F点为最新节点,更新最短路径数组。由于F点是最后一个点,所以也不用更新数组,目前的数组就是所求数组

    将F点加入最短路径范围中,此时所有的点都加入了最短路径范围,也就是说A点到所有点的距离都找到了。最总得出的距离值为:

    20200602131317346242.png

    最终得到的结果为:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    1|6最终结果

    相应的A点到所有点的最短路径走法最终得到的结果为:

    A

    B

    C

    D

    E

    F

    0

    6

    11

    4

    10

    16

    A-A:0

    A-B : A-D-B:6

    20200602131317410691.png

    A-C : A-D-E-C:11

    20200602131317504435.png

    A-D:4

    20200602131317674346.png

    A-E:A-D-E:10

    20200602131317745631.png

    A-F:A-D-E-C-F:16

    20200602131317851093.png

    1|7算法总结

    Dijkstra算法作为求最短路径的经典算法,个人理解为算法提供了一种思想,每走一步都是找到最短的路径,并且每走一步都实时更新所有距离,保证每次都选择最短路径。

    2|0python实现Dijkstra

    将以上的过程使用python来实现。

    首先总结一个Dijkstra算法的核心思想,分成两步走:

    构造一个最短路径数组,每次找到数组中未访问的节点里最小的点

    以上一步的节点为最新节点,更新起始点到所有点的距离

    使用python就是实现这两步即可

    一篇文章讲透Dijkstra最短路径算法-内有PHP-juepe运作缓存解答

    标签:需要   a算法   实现   三次   相同   个数   选择   动态规划   inf

    展开全文
  • 任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到...
  • 图的最短路径算法Dijkstra算法)的分析和代码实现。
  • Dijkstra 最短路径算法 Python 实现问题描述使用 Dijkstra 算法求图中的任意顶点到其它顶点的最短路径(求出需要经过那些点以及最短距离)。以下图为例:算法思想可以使用二维数组来存储顶点之间边的关系首先需要用一...
  • 迪杰斯特拉算法介绍迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。基本思想通过Dijkstra...
  • #include"Dijkstra.h" int main() { int ad[N][N]= { {1,13,8,65535,30,65535,32}, {65535,0,65535,65535,65535,9,7}, {65535,65535,0,5,65535,65535,65535}, {65535,65535,65535,0,6,65535,65535}, {65535,...
  • 于是今天就给大家带来一种时间复杂度是O(n²),的算法Dijkstra(迪杰斯特拉)。这个算法所求的是单源最短路,好比说你写好了Dijkstra的函数,那么只要输入点a的编号,就可算出图上每个点到这个点的距离。我先上一组...
  • Dijkstra最短路径算法

    2020-12-31 03:30:02
    示例伪代码分析Dijkstra算法是目前比较主流的计算最短路径的方法,求取一个顶点到其余各顶点的最短路径,也称作单源最短路径。它的主要特点是从起始点开始,采用贪心的策略对点进行遍历,层层遍历(广度优先搜索思想)...
  • 前段时间出于偶然的机遇,自己通过对Dijkstra算法的学习以及较为浅显的研究,写了Dijkstra最短路径算法的matlab程序,并且利用Floyd算法对同样的数据进行验证。曾经有段时间我一直在思考自己为什么要学习这些算法呢...
  • w,每一次都会选择distTo[]最小的来处理,在处理distTo[w]之前必须要能够保证distTo[v]已经是最小的最优的,这是保证最短路径条件成立的关键,局部最优解一步一步扩展到全局最优解,如同动态规划。 但是有一个问题...
  • 是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。 ...
  • } } //dijkstra算法实现:找到从startName点出发,到其他所有点的最短路径:选取自己定义的终点 public static List dijkstra(String startName, String endName) { List resList = new ArrayList(); PriorityQueue ...
  • 最短路径算法——迪杰斯特拉算法(Dijkstra) \qquad最短路径问题是在一个网络中求一条从出发点到目的点的最短路径。 \qquad这里会介绍求解有圈网络和无圈网络的2个算法:迪杰斯特拉算法(Dijkstra)、弗洛伊德算法...
  • 最短路径算法的一个文字解释。
  • 受这篇文章《SQL,NoSQL以及数据库的实质》结尾处题目的启发,我尝试写了一个SQL版本的Dijkstra最短路径算法。算法描述如下:前提假设:Hive支持Stored Procedure或者Mysql支持Insert into、insert overwrite、create ...
  • 在半年之前写过一篇关于无向图的构建以及相关常用算法的实现 → 图的构建以及BFS(广度优先搜索)、DFS(深度优先搜索)、普里姆最小生成树算法、并查集与kruskal算法 ,近日对这些算法进行了一个回顾,并且对其中的...
  • B站:dijkstra算法最短路径 看过之后就知道基本原理了。 算法实现步骤: ① 每次找出当前图中距离源点1最近的点k, ② 计算源点1经过该点k到达某个点j是否比原来更近,如果更近,则把源点1到某个点j的距离,替换为...
  • 本文依据“街区最短路径”这一问题讲解并实现Dijkstra算法(未建立类,代码量较少) 参考博文:最短路径问题—Dijkstra算法详解 最短路径问题—Dijkstra算法详解 算法特点: 迪科斯彻算法使用了广度优先搜索解决赋权...
  • Dijkstra算法(最短路径)

    2021-10-30 08:24:37
    U为源点 S为未添加数组 邻接矩阵存放的是权值,创建dist[]数组,用来存放结点间的距离,首先将v结点加入U集合... 再次在dist[]数组中找最短路径**在dist数组中找最短路径是在未添加的数组值那查找,已经添加到源点的...
  • 任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到...
  • 最短路径算法Dijkstra算法在路由选择中的应用.pdf计算机与网络江苏联合职业技术学院徐州机电工程分院 王恒青 江苏联合职业技术学院徐州生物工程分院 宋如敏[摘要】本文介绍了路由算法的设计目标以及种类,从最短路径...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼//运筹学之最短路径#include#include#defineM99999intmain(){intG[100][100];intn;intp[100],flag[100],s[100];intcur;intm,k,l,i,j;ifstreamfin("in.txt");//enterfin&...
  • Dijkstra算法的浅显说明
  • 每一次迭代产生一个永久标号,把它接入到以起始点为v0根的树中,在这棵树上每一个顶点与根结点之间的路径皆为最短路径。 1.3实例 寻找从顶点1到顶点5的最短路径: 一共有六个顶点,生成的带权邻接矩阵为:

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,979
精华内容 15,591
关键字:

dijkstra最短路径算法

友情链接: reduce_action.rar