单源最短路径算法 Dijkstra和Bellman-Ford

常用的单源最短路径算法一共有两个，一个是Dijkstra算法 ，一个是Bellman-ford 算法
Dijkstra 算法 不能处理含有负权边的图，Bellmanford 能够处理含负权边或包含负权回路的图。

 

首先是Dijkstra算法: 
算法的具体思想就不多写了，算法导论上有很详细的介绍，我主要还是贴出一个代码实现。

Dijstra里面需要用到优先级队列这里笔者也给出了一个。

使用堆实现的优先级队列，Dijkstar的复杂度在VlogV。

 

优先队列：

package graphic;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class PriorityQueue<E> {
	private final static int ROOT_INDEX =0;
	private List<E> heap ;
	protected Comparator<E> comparator;
	
	public PriorityQueue() {
		heap =  new ArrayList<E>();
	}
	public PriorityQueue(Comparator<E> comparator){
		this.comparator = comparator;
		heap = new ArrayList<E>();
	}
	
	public void insert(E obj){
		heap.add(obj);
		int index = heap.size()-1;
		
		adjustHeapUP(index);
	} 
	
	public void decreaseKey(E obj){
		for(int i =0;i<heap.size();i++){
			E cur = heap.get(i);
			if(cur.equals(obj)){
				adjustHeapUP(i);
				break;
			}
		}
	}
	
	public E extractMin(){
		if(heap.isEmpty()){throw new RuntimeException();}
		int index = heap.size()-1;
		E min = heap.get(ROOT_INDEX);
		E last = heap.get(index);
		heap.set(ROOT_INDEX, last);
		heap.remove(index);
		adjustHeapDown(ROOT_INDEX);
		
		return min;
	}
	
	protected void adjustHeapDown(int index){
		
		int p = index;
		int target = 2*p+1;
		if(target >= heap.size())return;
		
		if(target+1 < heap.size() && compare(heap.get(target),heap.get(target+1)) >0 ){
			target ++;
		}
		
		E paret = heap.get(p);
		E t = heap.get(target);
		if(compare(paret, t) > 0){
			heap.set(p, t);
			heap.set(target, paret);
			adjustHeapDown(target);
		}
		
		
	}
	protected int compare(E src,E des){
		if(comparator==null){
			Comparable<E> s1 = (Comparable<E>)src;
			Comparable<E> s2 = (Comparable<E>)des;
			return s1.compareTo((E) s2);
		}else{
			return comparator.compare(src, des);
		}
	}
	
	protected void adjustHeapUP(int index){
		int parent = parent(index);
		E p = heap.get(parent);
		E cur = heap.get(index);
	     
			if(compare(cur,p)<0){
				heap.set(index, p);
				heap.set(parent, cur);
				adjustHeapUP(parent);
			}
		
		}
		
	public void print(){
		for(E e:heap){
			System.out.println(e);
		}
		System.out.println();
	}
	
	protected int parent(int index){
		return (index-1)/2;
	}
	
	public boolean isEmpty(){
		return heap.isEmpty();
	}
	
}

 Dijkstra算法：

package graphic;

import java.util.List;

public class Dijkstra {
	static  int NODE_NUM =0 ;
	GNode[] nodes ;
	PriorityQueue<GNode> queue = new PriorityQueue<GNode>();
	
	
	public void addNode(int[] ids){
		NODE_NUM = ids.length;
		nodes = new GNode[NODE_NUM+1];
		for(Integer id:ids){
			nodes[id] = new GNode(id);
		}
	}
	
	public void addDirectionEdge(int src,int des,int weight){
		GEdge edge = new GEdge(nodes[src],nodes[des],weight);
		nodes[src].edges.add(edge);
	}
	
	public void addUnDirectedEdge(int src,int des,int weight){
		addDirectionEdge(src,des,weight);
		addDirectionEdge(des,src,weight);
	}
	
	public void shortPath(int src,int des){
		nodes[src].dis=0;
		for(int i=1;i<nodes.length;i++){
			queue.insert(nodes[i]);
		}
		while(!queue.isEmpty()){
			GNode min = queue.extractMin();
			if(min.nodeId == des){
				printShortPath(min);
				return;
			}
			List<GEdge> edges = min.edges;
			for(GEdge edge:edges){
				
				GNode ed = edge.des;
				if(min.dis+edge.weight < ed.dis){
					ed.dis = min.dis+edge.weight;
					queue.decreaseKey(ed);
					ed.parent = min;
					
				}
			}
		}
		
	}
	
	private void printShortPath(GNode node){
		
		if(node.parent!=null){
			printShortPath(node.parent);
			System.out.println(node.nodeId);
			
		}
		
	}
	
	public static void main(String[] args) {
		Dijkstra dij = new Dijkstra();
		dij.addNode(new int[]{1,2,3,4,5});
		dij.addUnDirectedEdge(1, 2, 1);
		dij.addUnDirectedEdge(1, 3, 1);
		dij.addUnDirectedEdge(2, 4, 2);
		dij.addUnDirectedEdge(3, 4, 3);
		dij.addUnDirectedEdge(4, 5, 3);
		dij.shortPath(1, 5);
	}
	
}

 

BellFord-man 算法：

对边进行迭代的算法，需要迭代|V|-1 次

复杂度为 O(EV)

package graphic;

import java.util.ArrayList;
import java.util.List;

public class BellmanFord {
	static  int NODE_NUM =0 ;
	GNode[] nodes ;
	List<GEdge> edges  = new ArrayList<GEdge>();
	
	public void addNode(int[] ids){
		NODE_NUM = ids.length;
		nodes = new GNode[NODE_NUM+1];
		for(Integer id:ids){
			nodes[id] = new GNode(id);
		}
	}
	
	public void addEdge(int src,int des,int weight){
		GEdge edge = new GEdge(nodes[src],nodes[des],weight);
		edges.add(edge);
	}
	
	public boolean shortestPath(int src){
		nodes[src].dis = 0;
		for(int i=1;i<NODE_NUM;i++){
			for(GEdge edge:edges){
				GNode start = edge.src;
				GNode end = edge.des;
				if(start.dis+edge.weight < end.dis){
					end.dis = start.dis+edge.weight;
					end.parent = start;
				}
			}
		}
		for(GEdge edge:edges){
			GNode start = edge.src;
			GNode end = edge.des;
			if(start.dis+edge.weight < end.dis){
				return false;
			}
		}
		
		return true;
		
	}
	
	public static void main(String[] args) {
		BellmanFord dij = new BellmanFord();
		dij.addNode(new int[]{1,2,3,4,5});
		dij.addEdge(1, 2, 1);
		dij.addEdge(1, 3, 1);
		dij.addEdge(2, 4, 2);
		dij.addEdge(3, 4, 3);
		dij.addEdge(4, 5, 3);
		dij.shortestPath(1);
		
		for(int i=1;i<=NODE_NUM;i++){
			System.out.println(dij.nodes[i].dis);
		}
	}
}

 

边和点的数据结构：

package graphic;

public class GEdge {
	GNode src;
	GNode des;
	int weight = 0 ;
	
	public GEdge(GNode src,GNode des,int weight) {
		this.src = src;
		this.des = des;
		this.weight = weight;
	}
	
	
}

package graphic;

import java.util.ArrayList;
import java.util.List;

public class GNode implements Comparable<GNode>{
	int nodeId;
	GNode parent = null;
	int dis = Integer.MAX_VALUE;
	int discoverTime =0;
	int finishTime =0;
	Color color = Color.White;
	List<GEdge> edges = new ArrayList<GEdge>();
	
	
	public GNode(Integer id) {
		this.nodeId = id;
	}
	public int getNodeId() {
		return nodeId;
	}
	public void setNodeId(int nodeId) {
		this.nodeId = nodeId;
	}
	public GNode getParent() {
		return parent;
	}
	public void setParent(GNode parent) {
		this.parent = parent;
	}
	public int getDis() {
		return dis;
	}
	public void setDis(int dis) {
		this.dis = dis;
	}
	public int getDiscoverTime() {
		return discoverTime;
	}
	public void setDiscoverTime(int discoverTime) {
		this.discoverTime = discoverTime;
	}
	public int getFinishTime() {
		return finishTime;
	}
	public void setFinishTime(int finishTime) {
		this.finishTime = finishTime;
	}
	public Color getColor() {
		return color;
	}
	public void setColor(Color color) {
		this.color = color;
	}
	public List<GEdge> getEdges() {
		return edges;
	}
	public void setEdges(List<GEdge> edges) {
		this.edges = edges;
	}
	@Override
	public int compareTo(GNode arg0) {
		if(this.dis > arg0.dis){
			return 1;
		}else if(this.dis == arg0.dis)return 0;
		return -1;
	}
	
	@Override
	public boolean equals(Object obj) {
		return this.nodeId == ((GNode)obj).nodeId;
	}
	
	
	@Override
	public String toString() {
		return "id: "+nodeId+"\tdis: "+dis;
				
	}
}