查找有向图最短路径

老师有一个题:

使用狄克斯屈拉(Dikjstra)标号算法可得出解:

我用Java来实现了一下这个算法:

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import lombok.Data;

public class MinRoute {
	public static void main(String args[]) {
		List<Edge> edges=initGraph(); 
		//查找从v1到v7的最短路长及最短路线
		findMinDistance("1","7",edges);
	}
	public static List<Vertex> findMinDistance(String from,String to,List<Edge> edges){
		Vertex fromVertex=findVertex(from,edges);
		fromVertex.setMinLen(0);
		Set<Edge> passedEdge=new HashSet<Edge>();
		
		System.out.print("find path:"+fromVertex.getName()+"->");
		Vertex findVertex=recursionFindMinEdge(fromVertex.getName(),edges,passedEdge);
		while(findVertex!=null&&!findVertex.getName().equals(to)) {
			System.out.print(findVertex.getName()+"->");
			findVertex=recursionFindMinEdge(findVertex.getName(),edges,passedEdge);
			
		}
		if(findVertex!=null&&findVertex.getName().equals(to)) {
			System.out.println(findVertex.getName());
			System.out.println("find! the minPath is:");
			
			StringBuffer sb=new StringBuffer();
			sb.append(findVertex.getName()+" > ");
			Vertex minFromVertex=findVertex.getMinFrom();
			while(!minFromVertex.getName().equals(from)) {
				sb.append(minFromVertex.getName()+" > ");
				minFromVertex=minFromVertex.getMinFrom();
			}
			sb.append(from);
			System.out.println(sb.reverse().toString());
		}else {
			System.out.println("not find!");
		}
		return null;
		
		
		
		
		
		
		
	}
	private static Vertex recursionFindMinEdge(String from,List<Edge> edges,Set<Edge> passedEdge) {
		Vertex fromVertex=findVertex(from, edges);
		//查出以当前顶点为始点的，且始点未标号的边
		List<Edge> fromEdges=findFromEdge(from,edges);
		for(Edge edge:fromEdges) {
			Integer oldMinLen=edge.getMinLen();
			if(oldMinLen==null) {
				edge.setMinLen(edge.getLen()+fromVertex.getMinLen());
			}
		}
		passedEdge.addAll(fromEdges);
		
		//查出之前走过的，且始点未标号的边。找到最小路径的边，并设置其终点的minLen
		Edge minLenEdge=null;
		for(Edge edge:passedEdge) {
			if(edge.getTo().getMinLen()!=null) {
				continue;
			}
			if(minLenEdge==null||edge.getMinLen()<minLenEdge.getMinLen()) {
				minLenEdge=edge;
			}
		}
		Vertex findTargetVertex=minLenEdge.getTo();
		
		findTargetVertex.setMinLen(minLenEdge.getMinLen());
		findTargetVertex.setMinFrom(minLenEdge.getFrom());
		return findTargetVertex;
	}
	
	/**
	 * 初始化图
	 * @return 返回所有边
	 */
	private static List<Edge> initGraph() {
		Vertex v1=new Vertex("1");
		Vertex v2=new Vertex("2");
		Vertex v3=new Vertex("3");
		Vertex v4=new Vertex("4");
		Vertex v5=new Vertex("5");
		Vertex v6=new Vertex("6");
		Vertex v7=new Vertex("7");
		List<Edge> rst=Arrays.asList(
				new Edge(v1,v2, 8),
				new Edge(v1,v3, 6),
				new Edge(v1,v4, 2),

				new Edge(v2,v5, 5),

				new Edge(v3,v6, 4),
				new Edge(v3,v4, 2),
				new Edge(v3,v2, 5),

				new Edge(v4,v3, 3),
				new Edge(v4,v6, 2),

				new Edge(v5,v7, 5),

				new Edge(v6,v2, 3),
				new Edge(v6,v5, 10),
				new Edge(v6,v7, 7)
		);
		
		
		return rst;
	}
	private static Vertex findVertex(String name,List<Edge> edges) {
		for(Edge edge:edges) {
			if(edge.getFrom().getName().equals(name)) {
				return edge.getFrom();
			}else if(edge.getTo().getName().equals(name)){
				return edge.getTo();
			}
		}
		return null;
	}
	private static List<Edge> findFromEdge(String name,List<Edge> edges) {
		List<Edge> findEdges=new ArrayList<Edge>();
		for(Edge edge:edges) {
			if(edge.getFrom().getName().equals(name)) {
				findEdges.add(edge);
			}
		}
		return findEdges;
	}
	

}
//有向图始点
@Data
class Vertex{
	private String name;
	//临时变量，一次计算时从起点到这点的最小距离
	private Integer minLen;
	//临时变量，当得到最短路径时，记录上一个顶点
	private Vertex minFrom;
	
	public Vertex(String name) {
		this.name=name;
	}
	
}
@Data
class Edge{
	private Vertex from;
	private Vertex to;
	//距离
	private Integer len;
	//临时变量，一次计算时从起点到"to"点的最小距离
	private Integer minLen;
	public Edge(Vertex from,Vertex to,Integer len) {
		this.from=from;
		this.to=to;
		this.len=len;
	}
}

find path:1->4->6->3->2->7
find! the minPath is:
1 > 4 > 6 > 7