查找有向图最短路径

老师有一个题:

使用狄克斯屈拉(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


文/程忠 浏览次数:0次   2019-07-07 11:28:50

相关阅读

微信扫描-捐赠支持
加入QQ群-技术交流

评论:
点击刷新

↓ 广告开始-头部带绿为生活 ↓
↑ 广告结束-尾部支持多点击 ↑