带权图的最短路径算法(Dijkstra)实现

一,介绍

本文实现带权图的最短路径算法。给定图中一个顶点,求解该顶点到图中所有其他顶点的最短路径 以及 最短路径的长度。在决定写这篇文章之前,在网上找了很多关于Dijkstra算法实现,但大部分是不带权的。不带权的Dijkstra算法要简单得多(可参考我的另一篇:无向图的最短路径算法JAVA实现);而对于带权的Dijkstra算法,最关键的是如何“更新邻接点的权值”。本文采用最小堆作为辅助,以重新构造堆的方式实现更新邻接点权值。

对于图而言,存在有向图和无向图。本算法只需要修改一行代码,即可同时实现带权有向图的Dijkstra和带权无向图的Dijkstra。因为,不管图是否是有向的还是无向的,只是构造图的方式不一样而已,而 Dijkstra算法都是一样的。

Dijkstra算法的实现需要一个辅助堆,用来选取当前到源点的距离 最小的那个顶点,这里采用了最小堆来实现。用最小堆保存图中所有顶点到源点的距离,因为Dijkstra算法运行过程中,需要每次选取当前到源点 距离最短 的那个顶点,这步操作用“出堆”很容易实现,但是,当选出该顶点之后, 需要不断地更新该顶点的邻接点到源点的距离。而最小堆不能很好地支持这种更新操作(关于最小堆可参考:),这也是为什么《算法导论》中推荐使用菲波拉契堆或者配对堆实现Dijkstra算法的原因。

二,Dijkstra实现思路

①初始化,源点的距离初始化为0(源点到它自己的距离当然是0了),源点的前驱顶点为null(因为是从源点开始的嘛,求源点到图中所有其他顶点的minDistance...)。所有其他顶点的前驱顶点也初始化为null,且顶点的“距离”(dist)属性初始化为无穷大(Integer.MAX_VALUE),即其他顶点到源点的距离 为无穷大。

②构造堆。将所有的顶点按照“距离”属性(dist) 构造最小堆。显然,由于源点的“距离”属性为0,其他顶点的“距离”属性为Integer.MAX_VALUE,故最开始构造的堆的 堆顶元素为源点。

③只要堆中还存在元素(while循环),执行deleteMin从堆中删除堆顶元素,记该元素为v,寻找v的所有邻接点,更新v的所有邻接点的距离。怎么更新的呢?就是比较:❶v的邻接点到源点的距离(dist属性)   ;  ❷v到源点的距离(dist属性) 加上  v 到v的邻接点的这条 边的权值 

v的邻接点的距离(dist属性)取 ❶ ❷ 中较小的那个。

伪代码如下:

DIJKSTRA(G,w,s)
初始化
构造堆(Q=V(G))
while(!isEmpty(Q))
v=EXTRACT-MIN(Q)
foreach vertex v_adj belogns to Adj[v]
更新v的邻接点 v_adj

三,具体代码实现

在讲解具体实现前,先介绍下如何构造图。假设图中的数据存储在文件中,文件的格式如下:

带权图的最短路径算法(Dijkstra)实现

(图的顶点及边信息---暂且用无向图举例)

第一列代表顶点的编号(不用管) ;第二列表示 边的 起始顶点的标识(vertexLabel)

第三列表示 边的 终点的标识;第四列表示边的权值。比如,对于权值为1的那条边而言,它对应的 起始顶点编号为0,对应的结点顶点的编号为1

关于图的解释,可参考

这里由于是带权图,故边类(Edge.java)需要有一个权值(边的权值)。

    private class Edge{
private int weight;//边的权值(带权图)
private Vertex endVertex;
public Edge(int weight, Vertex endVertex) {
this.weight = weight;
this.endVertex = endVertex;
}

图采用的是邻接表实现,因此每个顶点都会有一个邻接点列表。

     private class Vertex implements Comparable<Vertex>
{
private String vertexLabel;//顶点标识
private List<Edge> adjEdges;//顶点的所有邻接边(点)
private int dist;//顶点到源点的最短距离
private Vertex preNode;//追溯最短路径 public Vertex(String vertexLabel){
this.vertexLabel = vertexLabel;
adjEdges = new LinkedList<Edge>();
dist = Integer.MAX_VALUE;
preNode = null;
} @Override
public int compareTo(Vertex v) {
if(this.dist > v.dist)
return 1;
else if(this.dist < v.dist)
return -1;
return 0;
}
}

①第4行 adjEdges 是顶点的邻接点列表,表明图采用的是邻接表存储。第5行 dist 表示的是该顶点到源点的最短距离(从而不需要一个单独的距离数组)。第6行preNode 表示该顶点的前驱顶点, 用来记录源点到该顶点路径中经历了哪些顶点。

②Vertex类实现了Comparable接口,因为需要将顶点存储到最小堆中,而最小堆存储的元素需要实现Comparable接口(可以进行顶点的比较)。

最关键的是实现Dijkstra算法中用到的最小堆。关于最小堆的实现,可参考:数据结构--堆的实现之深入分析 本程序就是用的它。

然后是 dijkstra 的具体实现代码:

     public void dijkstra(){
BinaryHeap<Vertex> heap = new BinaryHeap<WeightedGraph.Vertex>();
init(heap);//inital heap while(!heap.isEmpty())
{
Vertex v = heap.deleteMin();
List<Edge> adjEdges = v.adjEdges;//获取v的所有邻接点
for (Edge e : adjEdges) {
Vertex adjNode = e.endVertex;
//update
if(adjNode.dist > e.weight + v.dist){
adjNode.dist = e.weight + v.dist;
adjNode.preNode = v;
}
}//end for //更新之后破坏了堆序性质,需要进行堆调整,这里直接重新构造堆(相当于decreaseKey)
heap.buildHeap();
} }

①第7行,从堆中出一个距离源点路径最短的顶点。刚好符合堆的基本操作(删除堆顶元素),这里也体现了Dijkstra是个贪心算法。

②第8-10行,获取顶点的邻接点

③第12行--15行的if语句,执行更新操作。关于更新操作的具体解释,可参考上面的介绍。

④由于 ③中的更新操作,破坏了堆序的性质,故需要进行堆调整。但是如何调整呢?由于堆不支持将堆中某个结点的权值降低,故在第19行,直接再次建堆。以保证堆序性质 。但是这里的时间复杂度就大了,故推荐使用更好的数据结构来实现,如Fib堆,因为Fib堆的将某个结点的权值降低是很方便的。

时间复杂度简要分析如下:buildHeap()的时间复杂度为O(N),对于图中每个顶点v,出堆时都需要重新构造堆,故最坏情况下时间复杂度为O(V^2)

整个完整代码实现如下:

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map; public class WeightedGraph{
private class Vertex implements Comparable<Vertex>
{
private String vertexLabel;//顶点标识
private List<Edge> adjEdges;//顶点的所有邻接边(点)
private int dist;//顶点到源点的最短距离
private Vertex preNode;//前驱顶点 public Vertex(String vertexLabel){
this.vertexLabel = vertexLabel;
adjEdges = new LinkedList<Edge>();
dist = Integer.MAX_VALUE;
preNode = null;
} @Override
public int compareTo(Vertex v) {
if(this.dist > v.dist)
return 1;
else if(this.dist < v.dist)
return -1;
return 0;
}
} private class Edge{
private int weight;//边的权值(带权图)
private Vertex endVertex;
public Edge(int weight, Vertex endVertex) {
this.weight = weight;
this.endVertex = endVertex;
}
} private Map<String, Vertex> weightedGraph;//存储图(各个顶点)
private Vertex startVertex;//单源最短路径的起始顶点 //图的信息保存在文件中,从文件中读取成字符串graphContent
public WeightedGraph(String graphContent) {
weightedGraph = new LinkedHashMap<String, WeightedGraph.Vertex>();
buildGraph(graphContent);//解析字符串构造图
}
private void buildGraph(String graphContent){
String[] lines = graphContent.split("\n"); String startNodeLabel, endNodeLabel;
Vertex startNode, endNode;
int weight;
for(int i = 0; i < lines.length; i++){
String[] nodesInfo = lines[i].split(",");
startNodeLabel = nodesInfo[1];
endNodeLabel = nodesInfo[2];
weight = Integer.valueOf(nodesInfo[3]); endNode = weightedGraph.get(endNodeLabel);
if(endNode == null){
endNode = new Vertex(endNodeLabel);
weightedGraph.put(endNodeLabel, endNode);
} startNode = weightedGraph.get(startNodeLabel);
if(startNode == null){
startNode = new Vertex(startNodeLabel);
weightedGraph.put(startNodeLabel, startNode);
}
Edge e = new Edge(weight, endNode);
//对于无向图而言,起点和终点都要添加边
// endNode.adjEdges.add(e);
startNode.adjEdges.add(e);
}
startVertex = weightedGraph.get(lines[0].split(",")[1]);//总是以文件中第一行第二列的那个标识顶点作为源点
} public void dijkstra(){
BinaryHeap<Vertex> heap = new BinaryHeap<WeightedGraph.Vertex>();
init(heap);//inital heap while(!heap.isEmpty())
{
Vertex v = heap.deleteMin();
List<Edge> adjEdges = v.adjEdges;//获取v的所有邻接点
for (Edge e : adjEdges) {
Vertex adjNode = e.endVertex;
//update
if(adjNode.dist > e.weight + v.dist){
adjNode.dist = e.weight + v.dist;
adjNode.preNode = v;
}
}//end for //更新之后破坏了堆序性质,需要进行堆调整,这里直接重新构造堆(相当于decreaseKey)
heap.buildHeap();
} }
private void init(BinaryHeap<Vertex> heap){
startVertex.dist = 0;//源点到其自身的距离为0
for (Vertex v : weightedGraph.values()) {
heap.insert(v);
}
} public void showDistance(){
for (Vertex v : weightedGraph.values()) {
printPath(v);
System.out.println();
System.out.println("顶点 " + v.vertexLabel + "到源点" + startVertex.vertexLabel + " 的距离: " + v.dist);
}
} //打印源点到 end 顶点的 最短路径
private void printPath(Vertex end)
{
if(end.preNode != null)
printPath(end.preNode);
System.out.print(end.vertexLabel + "--> ");
}
}

buildGraph()方法中:如果是有向图,只需要起点添加边;如果是无向图,则起点和终点都需要添加边。但不管是有向图还是无向图Dijkstra算法都一样。

            Edge e = new Edge(weight, endNode);
//对于无向图而言,起点和终点都要添加边
// endNode.adjEdges.add(e);
startNode.adjEdges.add(e);

关于如何测试WeightedGraph.java,需要构造一个图。构造图:可参考有向图的拓扑排序算法JAVA实现 中的“完整代码实现”中的FileUtil.java 和 TestXXX.java

public class TestDijkstra {
public static void main(String[] args) {
String graphFilePath;
if(args.length == 0)
graphFilePath = "F:\\graph2.txt";
else
graphFilePath = args[0]; String graphContent = FileUtil.read(graphFilePath, null);
WeightedGraph graph = new WeightedGraph(graphContent);
graph.dijkstra(); graph.showDistance();
}
}
上一篇:web框架详解之tornado 一 模板语言以及框架本质


下一篇:"数学口袋精灵"bug的发现及单元测试