Dijkstra 最短路径

参照严蔚敏 吴伟民《数据结构（C语言版）》P187.

 

给出两个程序片段：图都对应下面的图

第一个：邻接矩阵 的实现。

第二个：邻接表 的实现。

 

理解的关键是：

1，第一条最短的路径就是v0-v2。

2，次短路径是，也是到Vk的最短路径，要么是V0-Vk，要么是V0-V2-Vk。

基于代码整理：

package abc.graph;

import java.util.Arrays;

public class MGraph {
	int vertexNum;
	int [][] adjMatrix;

	int INFINITY = 9999;

	MGraph(int vertexNum) {
		this.vertexNum = vertexNum;
		adjMatrix = new int[vertexNum][vertexNum];
		for(int i = 0; i < vertexNum; i++)
			Arrays.fill(adjMatrix[i], INFINITY);
	}

	void addArc(int vi, int vj) {
		this.addArc(vi, vj, 1);
	}

	void addArc(int vi, int vj, int cost) {
		if(vi < 0 || vi >= vertexNum)
			throw new RuntimeException("Not contain Vertex " + vi);
		if(vj < 0 || vj >= vertexNum)
			throw new RuntimeException("Not contain Vertex " + vj);
		adjMatrix[vi][vj] = cost;
	}
	
	void shortestPath_DIJ() {
		boolean[] final_ = new boolean[vertexNum];
		int[] d = new int[vertexNum];
		boolean[][] p = new boolean[vertexNum][vertexNum];
		for(int v = 0; v < vertexNum; ++v) {
			final_[v] = false; d[v] = adjMatrix[0][v];
			for(int w=0; w < vertexNum; ++w) p[v][w] = false;
			if(d[v] < INFINITY) { p[v][0] = true; p[v][v] = true;}
		}
		d[0] = 0; final_[0] = true;
		int min, v = 0;
		for(int i = 1; i<vertexNum; ++i) {
			min = INFINITY;
			for(int w=0; w<vertexNum; ++w)
				if(!final_[w])
					if(d[w] < min) {v=w; min=d[w];}
			final_[v] = true;
			for(int w=0; w<vertexNum; ++w)
				if(!final_[w] && (min + adjMatrix[v][w] < d[w])) {
					d[w] = min + adjMatrix[v][w];
					p[w] = p[v]; p[w][w] = true;
				}
		}
		System.out.println(Arrays.asList(final_));
		for(int i : d)
			System.out.println(i);
//		System.out.println(d);
		
		for(boolean[] a : p) {
			for(boolean i : a) {
					System.out.print(String.format("%-6b", i));
			}
			System.out.println();
		}
	}

	void print() {
		System.out.print("   ");
		for(int i = 0; i < vertexNum; i++)
			System.out.print(String.format("%-4d", i));
		System.out.println();

		int lable = 1;
		for(int[] a : adjMatrix) {
			System.out.print(lable++ + " [");
			for(int i : a) {
				if( i == INFINITY )
					System.out.print(String.format("%-4s", "∞"));
				else
					System.out.print(String.format("%-4d", i));
			}
			System.out.println(" ]");
		}
	}

	static MGraph createUndigraph() {
		MGraph mGraph = new MGraph(6);
		mGraph.addArc(0, 2, 10);	mGraph.addArc(0, 4, 30);	mGraph.addArc(0, 5, 100);
		mGraph.addArc(1, 2, 5);		
		mGraph.addArc(2, 3, 50);
		mGraph.addArc(3, 5, 10);
		mGraph.addArc(4, 3, 20);	mGraph.addArc(4, 5, 60);
		return mGraph;
	}

	public static void main(String[] args) {
		MGraph.createUndigraph().print();
		MGraph.createUndigraph().shortestPath_DIJ();
	}

}

 

输出 写道

0 1 2 3 4 5
1 [∞ ∞ 10 ∞ 30 100 ]
2 [∞ ∞ 5 ∞ ∞ ∞ ]
3 [∞ ∞ ∞ 50 ∞ ∞ ]
4 [∞ ∞ ∞ ∞ ∞ 10 ]
5 [∞ ∞ ∞ 20 ∞ 60 ]
6 [∞ ∞ ∞ ∞ ∞ ∞ ]
[[Z@16caf43]
0
9999
10
50
30
60
false false false false false false
false false false false false false
true false true true false false
true false false true true true
true false false true true true
true false false true true true

 代码输出 d正确，p不太正确。

 

 

 

修改链接：http://www.iteye.com/topic/633491

的实现：

 

package abc.Dijkstra.pack;

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

public class Client {
	public static void main(String[] args) {
		Point V0 = new Point("V0");
		Point V1 = new Point("V1");
		Point V2 = new Point("V2");
		Point V3 = new Point("V3");
		Point V4 = new Point("V4");
		Point V5 = new Point("V5");
		
		List<Point> points = new ArrayList<Point>();
		points.add(V0);
		points.add(V1);
		points.add(V2);
		points.add(V3);
		points.add(V4);
		points.add(V5);

		List<Edge> edges = new ArrayList<Edge>();
		edges.add(new Edge(V0, V2, 10));
		edges.add(new Edge(V0, V4, 30));
		edges.add(new Edge(V0, V5, 100));

		edges.add(new Edge(V1, V2, 5));
		
		edges.add(new Edge(V2, V3, 50));
		
		edges.add(new Edge(V3, V5, 10));

		edges.add(new Edge(V4, V3, 20));
		edges.add(new Edge(V4, V5, 60));

		
		Dijkstra dijkstra = new Dijkstra();
		dijkstra.setPoints(points);
		dijkstra.setEdges(edges);
		
		dijkstra.dijkstra(V0);
		dijkstra.display();
		
	}
}
class Dijkstra {

	private List<Point> points;

	private List<Edge> edges = new ArrayList<Edge>();
	private List<Edge> directPath = new ArrayList<Edge>();

	private List<Path> paths = new ArrayList<Path>();

	//当前变为红点的点
	private Point currentPoint;
	private Path currentPath;

	private final int INFINITY = 999999;

	//源点到当前红点的长度
	private double startToCurrent;

	public void init(Point source) {

		//设置路径的终点，开始时路径中有起点：V0， 各个终点，经过的点只有起始点。（可以起始点到终点没有路径）
		for (Point point : points) {
			if( point == source )
				continue;

			List<Point> redPoints = new ArrayList<Point>();
			redPoints.add(source);
			Path path = new Path(source, point, redPoints, INFINITY);
			paths.add(path);
		}
		
		for (Edge edge: edges) {
			if (edge.start == source) {
				directPath.add(edge);
			}
		}

		// 当起点和终点直接由路径的时候，设置初始的最小距离就是路径长度。没有的化最小距离为“无穷大”。
		for (Path path : paths) {
			for (Edge edge: directPath) {
				if (path.end == edge.end) {
					path.length = edge.length;
				}
			}
		}
	}

	public void dijkstra(Point source){
		init(source);
		System.out.println("init()");
		display();
		System.out.println("init()");
		for (int i = 0; i < paths.size(); i++) {
			System.out.println("======== start 0000 ==========");
			int minIndex = getPathMinIndex();

			double minDist = paths.get(minIndex).length;

			if (minDist == INFINITY) {
				System.out.println("有无法到达的顶点");
			} else if(i != paths.size() - 1 ) {
				//获取当前循环已经求出最短路径的点
				currentPoint = paths.get(minIndex).end;
				
				paths.get(minIndex).points.add(currentPoint);
				
				currentPath = paths.get(minIndex);
				
				startToCurrent = minDist;

				currentPoint.isRed = true;
			}

			for (Path path : paths) {
				/** 
				 * 在当前红点发生变化后，源点到其他点的路径也相应变化，通过当前红点，
				 * 之前不可到的点有可能变为可到达，
				 * 之前可到达的点路径长度会发生改变
				 * 所以要重置其他路径的长度
				 */
				if (path.end.isRed) {
					continue;
				}
				for (Edge edge: edges) {
					if (edge.start == currentPoint && edge.end == path.end) {
						double startToFringe = startToCurrent + edge.length;
						if(startToFringe < path.length) {
							path.points.add(currentPoint);
							path.points.clear();
							path.points.addAll(currentPath.points);
							path.length = startToFringe;
						}
					}
				}
			} // resetPaths();
			
			System.out.println("i = " + i + " ;;;;;;  indexMin =" +minIndex);
			System.out.println("currentPoint = " + currentPoint.name);
			display();
			System.out.println("======== end  11111 ==========");
		}
		System.out.println("======== end ==========");
	}

	/**
	 * 在路径集合中获取长度最小的索引值
	 * @return
	 */
	private int getPathMinIndex() {
		double minDist = INFINITY;
		int indexMin = 0;
		for (int i = 0; i < paths.size(); i++) {
			Path path = paths.get(i);
			if (!path.end.isRed && path.length < minDist) {
				minDist = path.length;
				indexMin = i;
			}
		}
		return indexMin;
	}

	public void display() {
		StringBuilder sb = new StringBuilder(32);
		for (Path path : paths) {
			System.out.print(path.source.name +"-->"+ path.end.name+": (");
			for (Point point : path.points) {
				sb.append(point.name+",");
			}
			sb.deleteCharAt(sb.length()-1);
			sb.append(")");
			System.out.print(String.format("%-20s", sb.toString()));
			System.out.println(path.length);

			sb.delete(0, sb.length());
		}
	}

	public void setPoints(List<Point> points2) {
		this.points = points2;
	}

	public void setEdges(List<Edge> edges2) {
		this.edges = edges2;
	}
}
class Point {
	String name;
	boolean isRed;
	boolean isSource;
	
	public Point(String name) {
		this.name = name;
	}
}
class Edge {
	Point start;
	Point end;
	int length;
	
	public Edge(Point start, Point end, int length) {
		this.start = start;
		this.end = end;
		this.length = length;
	}
}
class Path {
	Point source;
	Point end;
	List<Point> points;
	double length;

	public Path(Point source, Point end, List<Point> points, double length) {
		this.source = source;
		this.end = end;
		this.points = points;
		this.length = length;
	}
}

 

输出 写道

init()
V0-->V1: (V0) 999999.0
V0-->V2: (V0) 10.0
V0-->V3: (V0) 999999.0
V0-->V4: (V0) 30.0
V0-->V5: (V0) 100.0
init()
======== start 0000 ==========
i = 0 ;;;;;; indexMin =1
currentPoint = V2
V0-->V1: (V0) 999999.0
V0-->V2: (V0,V2) 10.0
V0-->V3: (V0,V2) 60.0
V0-->V4: (V0) 30.0
V0-->V5: (V0) 100.0
======== end 11111 ==========
======== start 0000 ==========
i = 1 ;;;;;; indexMin =3
currentPoint = V4
V0-->V1: (V0) 999999.0
V0-->V2: (V0,V2) 10.0
V0-->V3: (V0,V4) 50.0
V0-->V4: (V0,V4) 30.0
V0-->V5: (V0,V4) 90.0
======== end 11111 ==========
======== start 0000 ==========
i = 2 ;;;;;; indexMin =2
currentPoint = V3
V0-->V1: (V0) 999999.0
V0-->V2: (V0,V2) 10.0
V0-->V3: (V0,V4,V3) 50.0
V0-->V4: (V0,V4) 30.0
V0-->V5: (V0,V4,V3) 60.0
======== end 11111 ==========
======== start 0000 ==========
i = 3 ;;;;;; indexMin =4
currentPoint = V5
V0-->V1: (V0) 999999.0
V0-->V2: (V0,V2) 10.0
V0-->V3: (V0,V4,V3) 50.0
V0-->V4: (V0,V4) 30.0
V0-->V5: (V0,V4,V3,V5) 60.0
======== end 11111 ==========
======== start 0000 ==========
有无法到达的顶点
i = 4 ;;;;;; indexMin =0
currentPoint = V5
V0-->V1: (V0) 999999.0
V0-->V2: (V0,V2) 10.0
V0-->V3: (V0,V4,V3) 50.0
V0-->V4: (V0,V4) 30.0
V0-->V5: (V0,V4,V3,V5) 60.0
======== end 11111 ==========
======== end ==========
V0-->V1: (V0) 999999.0
V0-->V2: (V0,V2) 10.0
V0-->V3: (V0,V4,V3) 50.0
V0-->V4: (V0,V4) 30.0
V0-->V5: (V0,V4,V3,V5) 60.0

 输出的d和p都没有问题，但是d和p的更新过程不太和书给出的表格匹配。