欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

最短路径问题:Dijkstra算法

程序员文章站 2022-06-15 14:36:23
定义 所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和(称为路径长度)达到最小。 下面我们介绍两种比较常用的求最短路径算法: Dijkstra(迪杰斯特拉)算法 他的算法思想是按路径长度递增的次序一步一步并入来求取, ......

定义

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

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

dijkstra(迪杰斯特拉)算法

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

算法思想

首先,我们引入一个辅助向量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的权值之和。

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

算法描述

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

最短路径问题:Dijkstra算法

我们使用guava的valuegraph作为该图的数据结构,每个顶点对应一个visited变量来表示节点是在v中还是在s中,初始时s中只有顶点v0。然后,我们看看新加入的顶点是否可以到达其他顶点,并且看看通过该顶点到达其他点的路径长度是否比从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