当前位置: 澳门新濠3559 > 编程 > 正文

所谓最短路径问题是指,带权值的有向图采用邻

时间:2019-11-08 04:40来源:编程
迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法。本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实

迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法。本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实现在一个带权值的有向图中,选定某一个起点,求解到达其它节点的最短路径,来加深对算法的理解。

定义

所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和(称为路径长度)达到最小。

下面我们介绍两种比较常用的求最短路径算法:

文转:http://blog.csdn.net/zxq2574043697/article/details/9451887

1 算法原理

迪杰斯特拉(Dijkstra)算法是一个按照路径长度递增的次序产生的最短路径算法。下图为带权值的有向图,作为程序中的实验数据。

图片 1

其中,带权值的有向图采用邻接矩阵graph来进行存储,在计算中就是采用n*n的二维数组来进行存储,v0-v5表示数组的索引编号0-5,二维数组的值表示节点之间的权值,若两个节点不能通行,比如,v0->v1不能通行,那么$graph[0,1]=infty$ (采用计算机中最大正整数来进行表示)。那如何求解从v0每个v节点的最短路径长度呢?
图片 2
首先,引进一个辅助数组cost,它的每个值$cost[i]$表示当前所找到的从起始点v0到终点vi的最短路径的权值(长度花费),该数组的初态为:若从v0到vi有弧,则$cost[i]$为弧上的权值,否则置$cost[i]$为$infty$ 。显然,长度为:
$$
cost[j]=Min_i(graph[0,i] | v_i in V)
$$
的路径就是从v0出发的长度最短的一条最短路径。此路径为$(v_0,v_j)$ ,那么下次长度次短的路径必定是弧$(v_0,v_i)$ 上的权值$cost[i](v_i in V)$,或者是$cost[k](v_k in S)$ 和弧$(v_k,v_i)$ 的权值之和。其中V:待求解最短路径的节点j集合;S:已求解最短路径的节点集合。

其实迪杰斯特拉(Dijkstra)最短路径算法是上一篇文迷宫问题求解之“A*搜索”(二)所讲到的 A*搜索算法中的一个特例,当A *搜索算法中 h(n)函数为0的时候,那么它就是迪杰斯特拉算法,算法原理一样,只不过在写程序的时候稍微有点区别而已。

Dijkstra(迪杰斯特拉)算法

他的算法思想是按路径长度递增的次序一步一步并入来求取,是贪心算法的一个应用,用来解决单源点到其余顶点的最短路径问题。

 

2 算法流程

根据上面的算法原理分析,下面描述算法的实现流程。

  1. 初始化:初始化辅助数组cost,从v0出发到图上其余节点v的初始权值为:$cost[i]=graph[0,i]  |  v_i in V$ ;初始化待求节点S集合,它的初始状态为空集。

  2. 选择节点$v_j$ ,使得$cost[j]=Min ( cost[i] | v_i in V -S )$ ,$v_j$ 就是当前求的一条从v0出发的最短路径的终点,修改S集合,使得$S=Sbigcup V_j$ 。

  3. 修改从v0出发到节点V-S上任一顶点$v_k$ 可达的最短路径,若cost[j]+graph[j,k]<cost[k] ,则修改cost[k]为:cost[k]=cost[j]+graph[j,k] 。

  4. 重复操作2,3步骤,直到求解集合V中的所有节点为止。

其中最短路径的存储采用一个path整数数组,path[i]的值记录vi的前一个节点的索引,通过path一直追溯到起点,就可以找到从vi到起始节点的最短路径。比如起始节点索引为0,若path[3]=4, path[4]=0;那么节点v2的最短路径为,v0->v4->v3。

算法思想

首先,我们引入一个辅助向量D,它的每个分量D[i]表示当前找到的从起始节点v到终点节点vi的最短路径的长度。它的初始态为:若从节点v到节点vi有弧,则D[i]为弧上的权值,否则D[i]为∞,显然,长度为D[j] = Min{D[i] | vi ∈V}的路径就是从v出发最短的一条路径,路径为(v, vi)。
那么,下一条长度次短的最短路径是哪一条呢?假设次短路径的终点是vk,则可想而知,这条路径或者是(v, vk)或者是(v, vj, vk)。它的长度或者是从v到vk的弧上的权值,或者是D[j]和从vj到vk的权值之和。

一般情况下,假设S为已知求得的最短路径的终点集合,则可证明:一下条最短路径(设其终点为x)或者是弧(v, x)或者是中间只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明,假设此路径上有一个顶点不在S中,则说明存在一条终点不在S中而长度比此路径短的路径。但是这是不可能的。因为,我们是按路径常度的递增次序来产生个最短路径的,故长度比此路径端的所有路径均已产生,他们的终点必定在S集合中,即假设不成立。

因此下一条次短的最短路径的长度是:D[j] = Min{D[i] | vi ∈ V - S},其中,D[i]或者是弧(v, vi)的权值,或者是D[k](vk ∈ S)和弧(vk, vi)上权值之和。

一:

3 算法实现

采用c#语言对第2节中的算法流程进行实现,关键代码如下。

算法描述

假设现要求取如下示例图所示的顶点V0与其余各顶点的最短路径:

图片 3

Dijkstra算法示例图

我们使用Guava的ValueGraph作为该图的数据结构,每个顶点对应一个visited变量来表示节点是在V中还是在S中,初始时S中只有顶点V0。然后从nodes集合中遍历找出从V0出发到各节点路径最短的节点,并将该节点并入S中(即修改该节点的visited属性为true),此时就找到了一个顶点的最短路径。然后,我们看看新加入的顶点是否可以到达其他顶点,并且看看通过该顶点到达其他点的路径长度是否比从V0直接到达更短,如果是,则修改这些顶点的权值(即if (D[j] + arcs[j][k] < D[k]) then D[k] = D[j] + arcs[j][k])。然后又从{V

  • S}中找最小值,重复上述动作,直到所有顶点都并入S中。

第一步,我们通过ValueGraphBuilder构造图的实例,并输入边集:

MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed()
        .nodeOrder(ElementOrder.insertion())
        .expectedNodeCount(10)
        .build();
graph.putEdgeValue(V0, V2, 10);
graph.putEdgeValue(V0, V4, 30);
graph.putEdgeValue(V0, V5, 100);
graph.putEdgeValue(V1, V2, 5);
graph.putEdgeValue(V2, V3, 50);
graph.putEdgeValue(V3, V5, 10);
graph.putEdgeValue(V4, V3, 20);
graph.putEdgeValue(V4, V5, 60);

return graph;

初始输出结果如下:

nodes: [v0, v2, v4, v5, v1, v3], 
edges: {<v0 -> v5>=100, <v0 -> v4>=30, <v0 -> v2>=10, 
<v2 -> v3>=50, <v4 -> v5>=60, <v4 -> v3>=20, <v1 -> v2>=5, 
<v3 -> v5>=10}

为了不破坏graph的状态,我们引入一个临时结构来记录每个节点运算的中间结果:

private static class NodeExtra {
    public String nodeName; //当前的节点名称
    public int distance; //开始点到当前节点的最短路径
    public boolean visited; //当前节点是否已经求的最短路径(S集合)
    public String preNode; //前一个节点名称
    public String path; //路径的所有途径点
}

第二步,我们首先将起始点V0并入集合S中,因为他的最短路径已知为0:

startNode = V0;
NodeExtra current = nodeExtras.get(startNode);
current.distance = 0; //一开始可设置开始节点的最短路径为0
current.visited = true; //并入S集合
current.path = startNode;
current.preNode = startNode;

第三步,在当前状态下找出起始点V0开始到其他节点路径最短的节点:

NodeExtra minExtra = null; //路径最短的节点信息
int min = Integer.MAX_VALUE;
for (String notVisitedNode : nodes) {
    //获取节点的辅助信息
    NodeExtra extra = nodeExtras.get(notVisitedNode); 

    //不在S集合中,且路径较短
    if (!extra.visited && extra.distance < min) {
        min = extra.distance;
        minExtra = extra;
    }
}

第四步,将最短路径的节点并入集合S中:

if (minExtra != null) { //找到了路径最短的节点
    minExtra.visited = true; //并入集合S中
    //更新其中转节点路径
    minExtra.path = nodeExtras.get(minExtra.preNode).path + " -> " + minExtra.nodeName; 
    current = minExtra; //标识当前并入的最短路径节点
}

第五步,更新与其相关节点的最短路径中间结果:

/**
 * 并入新查找到的节点后,更新与其相关节点的最短路径中间结果
 * if (D[j] + arcs[j][k] < D[k]) D[k] = D[j] + arcs[j][k]
 */
//只需循环当前节点的后继列表即可(优化)
Set<String> successors = graph.successors(current.nodeName); 
for (String notVisitedNode : successors) {
    NodeExtra extra = nodeExtras.get(notVisitedNode);
    if (!extra.visited) {
        final int value = current.distance 
            + graph.edgeValueOrDefault(current.nodeName,
                notVisitedNode, 0); //D[j] + arcs[j][k]
        if (value < extra.distance) { //D[j] + arcs[j][k] < D[k]
            extra.distance = value;
            extra.preNode = current.nodeName;
        }
    }
}

第六步,输出起始节点V0到每个节点的最短路径以及路径的途径点信息

Set<String> keys = nodeExtras.keySet();
for (String node : keys) {
    NodeExtra extra = nodeExtras.get(node);
    if (extra.distance < Integer.MAX_VALUE) {
        Log.i(TAG, startNode + " -> " + node + ": min: " + extra.distance
                + ", path: " + extra.path); //path在运算过程中更新
    }
}

实例图的输出结果为:

 v0 -> v0: min: 0, path: v0
 v0 -> v2: min: 10, path: v0 -> v2
 v0 -> v3: min: 50, path: v0 -> v4 -> v3
 v0 -> v4: min: 30, path: v0 -> v4
 v0 -> v5: min: 60, path: v0 -> v4 -> v3 -> v5

具体Dijkstra算法的示例demo实现,请参考:https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/Dijkstra.java

最短路径算法

3.1 最短路径代码

class DijkstraSolution
{
    /*
        * 求解各节点最短路径,获取path,和cost数组,
        * path[i]表示vi节点的前继节点索引,一直追溯到起点。
        * cost[i]表示vi节点的花费
        */
    public static void FindShortestPath(int[,] graph,int startIndex, int[] path, int[] cost,int max)
    {
        int nodeCount = graph.GetLength(0);
        bool[] v = new bool[nodeCount];
        //初始化 path,cost,V
        for (int i = 0; i <nodeCount ; i++)
        {
            if (i == startIndex)//如果是出发点
            {
                v[i] = true;//
            }
            else
            {
                cost[i] = graph[startIndex,i ];
                if (cost[i] < max) path[i] = startIndex;
                else path[i] = -1;
                v[i] = false;
            }
        }
        //
        for(int i=1;i<nodeCount;i++)//求解nodeCount-1个
        {
            int minCost = max ;
            int curNode=-1;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w])//未在V集合中
                { 
                    if(cost[w]<minCost)
                    {
                        minCost = cost[w];
                        curNode = w;
                    }
                }
            }//for  获取最小权值的节点
            if (curNode == -1) break;//剩下都是不可通行的节点,跳出循环
            v[curNode] = true;
            for (int w = 0; w < nodeCount; w++)
            {
                if (!v[w] && (graph[curNode, w] + cost[curNode] < cost[w]))
                {
                    cost[w] = graph[curNode, w] + cost[curNode];//更新权值
                    path[w] = curNode;//更新路径
                }
            }//for 更新其他节点的权值(距离)和路径
        }//
    }
}

Floyd(弗洛伊德)算法

Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法,可以正确处理有向图或负权的最短路径问题。(动态规划算法是通过拆分问题规模,并定义问题状态与状态的关系,使得问题能够以递推(分治)的方式去解决,最终合并各个拆分的小问题的解为整个问题的解。)

1. 迪杰斯特拉算法

3.2 调用代码

int max = 10000;
int[,] graph = new int[6, 6] {
    {max,max,10,max,30,100},
    {max,max,5,max,max,max},
    {max,max,max,50,max,max},
    {max,max,max,max,max,10},
    {max,max,max,20,max,60},
    {max,max,max,max,max,max},
};
int []path = new int[6];
int []cost = new int[6];
DijkstraSolution.FindShortestPath(graph, 0, path, cost,max);

算法思想

从任意节点i到任意节点j的最短路径不外乎2种可能:1)直接从节点i到节点j,2)从节点i经过若干个节点k到节点j。所以,我们假设arcs(i,j)为节点i到节点j的最短路径的距离,对于每一个节点k,我们检查arcs(i,k)

  • arcs(k,j) < arcs(i,j)是否成立,如果成立,证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短,我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j),这样一来,当我们遍历完所有节点k,arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。(由于动态规划算法在执行过程中,需要保存大量的临时状态(即小问题的解),因此它天生适用于用矩阵来作为其数据结构,因此在本算法中,我们将不使用Guava-Graph结构,而采用邻接矩阵来作为本例的数据结构)

2. 弗洛伊德算法

3.3 运行结果

图片 4

算法分析及描述

假设现要求取如下示例图所示任意两点之间的最短路径:

图片 5

最短路径示例图

我们以一个4x4的邻接矩阵(二维数组arcs[ ][ ])作为图的数据结构。比如1号节点到2号节点的路径的权值为2,则arcs[1][2] = 2,2号节点无法直接到达4号节点,则arcs[2][4] = ∞(Integer.MAX_VALUE),则可构造如下矩阵:

图片 6

有向图的初始邻接矩阵

根据以往的经验,如果要让任意两个顶点(假设从顶点a到顶点b)之间的距离变得更短,唯一的选择就是引入第三个顶点(顶点k),并通过顶点k中转(a -> k ->b)才可能缩短顶点a到顶点b之间的距离。于是,现在的问题便分解为:求取某一个点k,使得经过中转节点k后,使得两点之间的距离可能变短,且还可能需要中转两个或者多个节点才能使两点之间的距离变短。比如图中的4号节点到3号节点(4 -> 3)的距离原本是12(arcs[4][3] = 12),如果在只通过1号节点时中转时(4 -> 1 ->3),距离将缩短为11(arcs[4][1] + arcs[1][3] = 5 + 6 = 11)。其实1号节点到3号节点也可以通过2号节点中转,使得1号到3号节点的路程缩短为5(arcs[1][2]

  • arcs[2][3] = 2 + 3 = 5),所以如果同时经过1号和2号两个节点中转的话,从4号节点到3号节点的距离会进一步缩短为10。于是,延伸到一般问题:
    1、当不经过任意第三节点时,其最短路径为初始路径,即上图中的邻接矩阵所示。
    2、当只允许经过1号节点时,求两点之间的最短路径该如何求呢?只需判断arcs[i][1]+arcs[1][j]是否比arcs[i][j]要小即可。arcs[i][j]表示的是从i号顶点到j号顶点之间的距离,arcs[i][1] + arcs[1][j]表示的是从i号顶点先到1号顶点,再从1号顶点到j号顶点的路程之和。循环遍历一遍二维数组,便可以获取在仅仅经过1号节点时的最短距离,实现如下:

    for (int i = 1; i <= vexCount; i++) {

      for (int j = 1; j < vexCount; j++) {
          if (arcs[i][1] + arcs[1][j] < arcs[i][j]) {
              arcs[i][j] = arcs[i][1] + arcs[1][j]; 
          }
      }
    

    }

由于上述代码更新了两点之间经过1号节点的最短距离arcs[i][j],因此,数组中每两个节点之间对应距离都是最短的。由于此时arcs[i][j]的结果已经保存了中转1号节点的最短路径,此时如果继续并入2号节点为中转节点,则是任意两个节点都经过中转节点1号节点和2号节点的最短路径,因为运算完中转1号节点时,arcs[i][j]的结果已经更新为中转1号节点的最短路径了。更一般的,继续并入下一个中转节点一直到vexCount个时,arcs[i][j]的结果保存的就是整个图中两点之间的最短路径了。这就是Floyd算法的描述,变成代码就是下面几行行:

for (int k = 1; k <= vexCount; k++) { //并入中转节点1,2,...vexCount
    for (int i = 1; i <= vexCount; i++) {
        for (int j = 1; j < vexCount; j++) {
            if (arcs[i][1] + arcs[1][j] < arcs[i][j]) {
                arcs[i][j] = arcs[i][1] + arcs[1][j];
                path[i][j] = path[i][k]; //这里保存当前是中转的是哪个节点的信息
            }
        }
    }
} 

对应到示例图的中间运算结果如下:

print array step of 1: //并入1号节点的结果
    0     2     6     4 
    ∞     0     3     ∞ 
    7     9     0     1 
    5     7    11     0 

print array step of 2: //并入2号节点的结果
    0     2     5     4 
    ∞     0     3     ∞ 
    7     9     0     1 
    5     7    10     0 

print array step of 3: //并入3号节点的结果
    0     2     5     4 
   10     0     3     4 
    7     9     0     1 
    5     7    10     0 

print array step of 4: //并入4号节点(图最终两两节点之间的最短路径值)
    0     2     5     4 
    9     0     3     4 
    6     8     0     1 
    5     7    10     0 

二:

4 总结

迪杰特拉斯算法求解了一个起始节点到所有其他节点的最短路径,时间复杂度为$O(n^2)$ ,即使人们可能只想知道从起始节点到某个特定的节点的最短路径,时间复杂度同样为$O(n^2)$ 。

理解一个算法和实现一个算法还有有些区别的。理解一个算法,只需要明白算法原理和它的逻辑过程即可,但是实现一个算法,不仅要明白算法的逻辑过程,还考究我们的程序设计能力。

虽然此时已求得了节点的最短路径,但结果却不能明显的表达最终最短路径是中转了哪些节点,因此这里对应到动态规划算法中的强项——算法过程中可以完全记录所有的中间结果。我们再定义一个二位数组path[][],其大小规模对应arcs[][],初始结果path[i][j]

1. 迪杰斯特拉算法

5 参考资料和资源

参考资料:严蔚敏的《数据结构c语言版》

源代码:

j,表示节点i到节点j最后的中转节点是j。在运算中是在判断arcs[i][k]+arcs[k][j]比arcs[i][j]要小时,我们进一步更新为:path[i][j]

path[i][k],即当前最短路径的最后中转节点是path[i][k]对应的节点(如果只允许中专一个节点时即为k,但中转多个节点时,需要对应上一步的中转节点,因此这里要指明是path[i][k]而不是k)。
于是我们通过向前递推path[][]数组,直到path[i][j]是目标节点。则可输出其中转节点,输出函数实现如下:

private void printPath(int arcs[][], int path[][], int vexCount) {
    int temp;
    for (int i = 1; i <= vexCount; i++) {
        StringBuilder builder = new StringBuilder();
        for (int j = 1; j <= vexCount; j++) { //遍历打印任意亮点的路径
            builder.append(i).append("->").append(j)
                .append(", weight: "). append(arcs[i][j])
                    .append(":").append(i);
            temp = path[i][j];
            while(temp != j) {
                builder.append("->").append(temp);
                temp = path[temp][j];
            }
            builder.append("->").append(j).append("n");
        }
        Log.i(TAG, builder.toString());
    }
}

对应示例图的最短路径的中转节点结果输出如下:

 1->1, weight: 0, path: 1->1
 1->2, weight: 2, path: 1->2
 1->3, weight: 5, path: 1->2->3
 1->4, weight: 4, path: 1->4
 2->1, weight: 9, path: 2->3->4->1
 2->2, weight: 0, path: 2->2
 2->3, weight: 3, path: 2->3
 2->4, weight: 4, path: 2->3->4
 3->1, weight: 6, path: 3->4->1
 3->2, weight: 8, path: 3->4->1->2
 3->3, weight: 0, path: 3->3
 3->4, weight: 1, path: 3->4
 4->1, weight: 5, path: 4->1
 4->2, weight: 7, path: 4->1->2
 4->3, weight: 10, path: 4->1->2->3
 4->4, weight: 0, path: 4->4

具体Floyd算法的示例demo实现,请参考:https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/Floyd.java

求从源点到其余各点的最短路径

参考文档

《数据结构》(严蔚敏版)
http://developer.51cto.com/art/201403/433874.htm

依最短路径的长度递增的次序求得各条路径

路径长度最短的最短路径的特点:

在这条路径上,必定只含一条弧,并且这条弧的权值最小

下一条路径长度次短的最短路径的特点:

它只可能有两种情况:或是直接从源点到该点(只含一条弧);或者是从源点经过顶点v1,再到达该顶点(由两条弧组成)。

再下一条路径长度次短的最短路径的特点:

它可能有三种情况:或者是直接从源点到该点(只含一条弧);或者是从源点经过顶点v1,再到达该顶点(由两条弧组成);或者是从源点经过顶点v2,再到达该顶点。

其余最短路径的特点:

它或者是直接从源点到该点(只含一条弧);或者是从源点经过已求得最短路径的顶点,再到达该顶点。

迪杰斯特拉算法

算法:

(a) 初始化:用起点v到该顶点w的直接边(弧)初始化最短路径,否则设为∞;

(b)从未求得最短路径的终点中选择路径长度最小的终点u:即求得v到u的最短路径;

(c) 修改最短路径:计算u的邻接点的最短路径,若(v,…,u)+(u,w)<(v,…,w),则以(v,…,u,w)代替。

(d) 重复(b)-(c),直到求得v到其余所有顶点的最短路径。

特点:总是按照从小到大的顺序求得最短路径

顶点A到其他顶点的最短路径

图片 7

图片 8

Dijkstra算法可描述如下:

初始化:S← { v0 }; 

         dist[j] ←Edge[0][j],   j = 1, 2, …, n-1;

                                         // n为图中顶点个数

· 求出最短路径的长度:

         dist[k] ← min{ dist[i] },  iÎ*VS *;

         SSU { k};

¸ 修改: 

      dist[i] ← min{ dist[i], dist[k] + Edge[k][i] },

               对于每一个iÎ*VS *;

¹ 判断:  若S = V, 则算法结束,否则转

 

二:

弗洛伊德算法

求每对顶点之间的最短路径。

依次计算矩阵A(0),A(1),…,A(n)。

A(0)为邻接矩阵,

计算A(k)时,
A(k)(i,j)=min{A(k-1)(i,j), A(k-1)(i,k)+A(k-1)(k,j)}。

A(0) [i][j]是从顶点vi vj , 中间顶点是v0的最短路径的长度,  A(k) [i][j]是从顶点vi vj ,  中间顶点的序号不大于k的最短路径的长度, A(n-1)[i][j]是从顶点vi vj 的最短路径长度。

 

 

弗洛伊德算法的基本思想是:

从 vi 到 vj 的所有可能存在的路径中,选出一条长度最短的路径。

n 次试探:

若<vi,vj>存在,则存在路径{vi,vj}

                // 路径中不含其它顶点

若<vi,v0>,<v0,vj>存在,则存在路径{vi,v0,vj}

             // 路径中所含顶点序号不大于0

若{vi,…,v1}, {v1,…,vj}存在,

   则存在一条路径{vi, …, v1, …vj}

             // 路径中所含顶点序号不大于1

      …

依次类推,则 vi 至 vj 的最短路径应是上述这些路径中,路径长度最小者

 

求每对顶点之间的最短路径

图片 9

 

图片 10

图片 11

图片 12

 

 

弗洛伊德算法

技巧:计算A(k)的技巧。

第k行、第k列、对角线的元素保持不变,对其余元素,考查A(i,j)与A(i,k)+A(k,j)(第k列i“行”元素加上第k行j“列”元素,简记为“行+列”),如果后者更小则替换A(i,j),同时修改路径。

图片 13

本节给出的求解最短路径的算法不仅适用于带权有向图,对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图,只要在顶点vi vj 之间存在无向边(vi vj ),就可以看成是在这两个顶点之间存在权值相同的两条有向边< vi vj >和< vj vi >。

试利用Dijkstra算法求下图中从顶点1到其他各顶点间的最短路径,写出执行算法过程中各步的状态

 

图片 14

 

编辑:编程 本文来源:所谓最短路径问题是指,带权值的有向图采用邻

关键词:

  • 上一篇:没有了
  • 下一篇:没有了