基于无向图且权重单一的最短路径Dijkstra算法——JAVA实现

设计模式 前端之家
前端之家收集整理的这篇文章主要介绍了基于无向图且权重单一的最短路径Dijkstra算法——JAVA实现，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

做一个无向图的权重单一的最短路径算法。

模拟停车场最近车位的选择。


首先参考了博友JavaMan_chen的博文
http://www.jb51.cc/article/p-oqcwtqrd-ov.html

但是这个算法是有问题的。

算法中，如果A点是当前点，是选取距离A点权重最小的那一点作为下一个路径点的。

这就带来了一个问题，即，距离A点的2个点如果权重相同，那就会随机选取其中一条。

于是，在数据量稍微大点的时候，就出错了。

在这里使用Dijkstra算法使用的是用OPEN,CLOSE表的方式。

首先，定义了坐标点的数据结构

Coordinate.java

Coordinate中包含相邻坐标的List，以及距离起始点的距离。

在算法中，一开始要进行所有路径点的关联。

之后，通过从起始点进行扩散，将所有点的step计算出来。

package com.harlan.dijkstra;  
  
import java.util.LinkedList;  
  
  
/** 
 * 坐标点的数据结构 
 *  
 * @author Harlan 
 *  
 */  
public class Coordinate {  
    //x坐标  
    public int x;  
    //y坐标  
    public int y;  
    //相邻坐标  
    public LinkedList<Coordinate> adj;  
    //距离  
    public int steps;  
    // 最短路径中的前一个顶点  
    public Coordinate lastPoint;  
;  
  
    public Coordinate(){  
          
    }  
      
    public Coordinate(int newX,int newY) {  
        x = newX;  
        y = newY;  
        adj=new LinkedList<Coordinate>();  
        reset();  
    }  
      
    public void reset(){  
        steps=Integer.MAX_VALUE;  
        lastPoint=null;  
    }  
  
    @Override  
    public boolean equals(Object obj) {  
        if (!(obj instanceof Coordinate))  
            return false;  
  
        Coordinate other = (Coordinate) obj;  
        if (x == other.x && y == other.y) {  
            return true;  
        }  
        return false;  
    }  
      
    @Override  
    public int hashCode() {  
        return x*10000+y;  
    }  
  
    /** 
     * 以JSON格式展示坐标 
     */  
    @Override  
    public String toString() {  
        return "{\"x\":" + x + ",\"y\":" + y + "}";  
    }  
}

并定义了路径数据结构

PathInfo.java

import java.util.List;  
  
/** 
 * 路径信息 
 * @author Harlan 
 * 
 */  
public class PathInfo {  
  
    //目标点的坐标  
    private Coordinate targetCd;  
      
    //去往目标点的最佳路径  
    private List<Coordinate> cdList;  
  
    public Coordinate getTargetCd() {  
        return targetCd;  
    }  
  
    public void setTargetCd(Coordinate targetCd) {  
        this.targetCd = targetCd;  
    }  
  
    public List<Coordinate> getCdList() {  
        return cdList;  
    }  
  
    public void setCdList(List<Coordinate> cdList) {  
        this.cdList = cdList;  
    }  
      
      
}


在算法中，对于路径点的关联方法：

<span style="white-space:pre">	</span> /**
	 * 和周围的四个点建立关系
	 * 
	 * @param node
	 */
	private void getContactWithF(Coordinate node) {
		Coordinate coordinate = getCoordinate(node);
		Coordinate EAST = new Coordinate(node.x + 1,node.y);
		Coordinate SOUTH = new Coordinate(node.x,node.y + 1);
		Coordinate WEST = new Coordinate(node.x - 1,node.y);
		Coordinate NORTH = new Coordinate(node.x,node.y - 1);
		if (isCellSafe(EAST,mRoads)) {
			EAST = getCoordinate(EAST);
			coordinate.adj.add(EAST);
		}
		if (isCellSafe(SOUTH,mRoads)) {
			SOUTH = getCoordinate(SOUTH);
			coordinate.adj.add(SOUTH);
		}
		if (isCellSafe(WEST,mRoads)) {
			WEST = getCoordinate(WEST);
			coordinate.adj.add(WEST);
		}
		if (isCellSafe(NORTH,mRoads)) {
			NORTH = getCoordinate(NORTH);
			coordinate.adj.add(NORTH);
		}
	}

/**
	 * 判断周围的位子是不是道路
	 * 
	 * @param head
	 * @return
	 */
	public boolean isCellSafe(Coordinate park,Set<Coordinate> roads) {
		boolean isSafe = false;
		// 在道路集合里面，就是安全的，否则，不安全
		for (Coordinate info : roads) {
			if (info.equals(park)) {
				isSafe = true;
			}
		}
		return isSafe;
	}

无权最短路径的算法如下: 

  <span style="white-space:pre">	</span>// 无权最短路径计算
	public void unweighted(Coordinate enter) {

		if (enter == null)
			throw new NoSuchElementException("Start vertex not found!");

		LinkedList<Coordinate> q = new LinkedList<Coordinate>();
		
		clearAll();
		enter = vertexMap.get(enter.toString());

		System.out.println("unweighted Harlan:" + enter.adj.toString());

		q.addLast(enter);

		enter.steps = 0;

		while (!q.isEmpty()) {
			Coordinate v = q.removeFirst();
			for (Iterator<Coordinate> itr = v.adj.iterator(); itr.hasNext();) {
				Coordinate w = itr.next();
				if (w.steps == Integer.MAX_VALUE) {
					w.steps = v.steps + 1;
					w.lastPoint = v;
					q.addLast(w);
				}
			}
		}
	}

遍历获取实际最短路径 

<span style="white-space:pre">	</span>private List<Coordinate> getPath(Coordinate dest,List<Coordinate> cdList) {
		if (dest.lastPoint != null) {
			cdList = (getPath(dest.lastPoint,cdList));
		}
		cdList.add(dest);
		return cdList;
	}


显示最短路径: 

<span style="white-space:pre">	</span>// 显示一条路径
	public void printPath(String coodrStr) throws NoSuchElementException {
		Coordinate coord = vertexMap.get(coodrStr);
		if (coord == null)
			throw new Exception(No path  found!");
		else if (coord.steps == Integer.MAX_VALUE)
			System.out.println(coord.toString() + "is unreachable!");
		else {
			printPath(coord);
			System.out.println();
		}
	}

	// 显示实际最短路径
	private void printPath(Coordinate dest) {

		if (dest.lastPoint != null) {
			printPath(dest.lastPoint);
			System.out.print(",");
		}
		System.out.print(dest.toString());
	}


最后，写一个对外的使用类，便可以在Android或者其他地方使用了 .

GetDijkstraPath.java

package com.harlan.dijkstra;

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

public class GetDijkstraPath {

	private static final String TAG = GetDijkstraPath.class.getSimpleName();
	
	/**
	 * 主函数，测试类
	 * @param args
	 */
	 public static void main(String[] args) {  
	    	Coordinate enter = new Coordinate(2,0);
		
	    	Set<Coordinate> roads = new HashSet<Coordinate>();
	    	roads.add(new Coordinate(3,10));
	    	roads.add(new Coordinate(3,11));
	    	roads.add(new Coordinate(3,8));
	    	roads.add(new Coordinate(3,9));
	    	roads.add(new Coordinate(3,6));
	    	roads.add(new Coordinate(3,7));
	    	roads.add(new Coordinate(3,4));
	    	roads.add(new Coordinate(3,5));
	    	roads.add(new Coordinate(3,2));
	       	roads.add(new Coordinate(3,3));
	    	roads.add(new Coordinate(3,1));
	    	roads.add(new Coordinate(6,1));
	    	roads.add(new Coordinate(1,9));
	    	roads.add(new Coordinate(1,8));
		roads.add(new Coordinate(1,11));
		roads.add(new Coordinate(1,10));
		roads.add(new Coordinate(1,5));
		roads.add(new Coordinate(1,4));
		roads.add(new Coordinate(1,7));
		roads.add(new Coordinate(1,6));
		roads.add(new Coordinate(1,1));
		roads.add(new Coordinate(1,3));
		roads.add(new Coordinate(1,2));
		roads.add(new Coordinate(4,1));
		roads.add(new Coordinate(4,11));
		roads.add(new Coordinate(7,5));
		roads.add(new Coordinate(7,4));
		roads.add(new Coordinate(2,11));
	    	roads.add(new Coordinate(7,7));
	    	roads.add(new Coordinate(7,6));
	    	roads.add(new Coordinate(7,1));
	    	roads.add(new Coordinate(7,3));
	    	roads.add(new Coordinate(7,2));
	    	roads.add(new Coordinate(2,9));
	    	roads.add(new Coordinate(7,8));
	    	roads.add(new Coordinate(7,10));
	    	roads.add(new Coordinate(5,11));
	    	roads.add(new Coordinate(5,9));
	    	roads.add(new Coordinate(5,8));
	    	roads.add(new Coordinate(5,7));
	    	roads.add(new Coordinate(5,6));
	    	roads.add(new Coordinate(5,5));
	    	roads.add(new Coordinate(5,4));
	    	roads.add(new Coordinate(5,3));
	    	roads.add(new Coordinate(5,2));
	    	roads.add(new Coordinate(5,1));
	    	System.out.println("nearest roads.size(): "+roads.size());
	    	
	    	
	    	Set<Coordinate> trags = new HashSet<Coordinate>();
	    	trags.add(new Coordinate(5,4));
	    	trags.add(new Coordinate(5,5));
	    	PathInfo nearest = getNearestPathInfo(roads,trags,enter);
	    	System.out.println("nearest : "+nearest.getCdList());
	    }  
	
	 
	 /**
	  * 对外的接口(如果计算多入口的最短路径的时候使用)
	  * 获取多入口的最佳路径
	  * @param roads
	  * @param trags
	  * @param enters
	  * @return
	  */
	 public static PathInfo getNearestPathInfoFromDiffEnter(Set<Coordinate> roads,Set<Coordinate> trags,Set<Coordinate> enters){
		 List<PathInfo> list = new ArrayList<>();
		 for(Coordinate enter:enters){
			 list.add(getNearestPathInfo(roads,enter));
		 }
		 //每条路径的步长
		 int steps = Integer.MAX_VALUE;
		 PathInfo nearste = new PathInfo();
		 for(PathInfo pathInfo:list){
			 if(pathInfo.getCdList().size()<steps){
				 steps = pathInfo.getCdList().size();
				 nearste = pathInfo;
			 }
		 }
		 return nearste;
		 
	 }
	 
	 
	 /**
	  * 对外的接口(如果计算单一入口的最短路径时候使用)
	  * 获取单一入口的最佳路径
	  * 
	  * @param roads
	  * @param trags
	  * @param enter
	  * @return
	  */
	 public static PathInfo getNearestPathInfo(Set<Coordinate> roads,Coordinate enter){
		 List<PathInfo> list = getAllAvailablePathInfo(roads,enter);
//		 for(PathInfo info:list){
//	    		System.out.println("getNearestPathInfo targ:"+info.getTargetCd());
//	    		System.out.println("getNearestPathInfo route:"+info.getCdList());
//	    		System.out.println("getNearestPathInfo *********************");
//	    	}
//		 
		 //每条路径的步长
		 int steps = Integer.MAX_VALUE;
		 PathInfo nearste = new PathInfo();
		 for(PathInfo pathInfo:list){
			 if(pathInfo.getCdList().size()<steps){
				 steps = pathInfo.getCdList().size();
				 nearste = pathInfo;
			 }
		 }
		 return nearste;
	 }
	 
	
	/**
	 * 获取到达所有目标点的所有可用路径
	 * 
	 * @param roads
	 * @param trags
	 * @param enter
	 * @return
	 */
	private static List<PathInfo> getAllAvailablePathInfo(Set<Coordinate> roads,Coordinate enter) {
		Set<Coordinate> availableRoadTar = getAllRoadNearTarg(roads,trags);
		
    	//计算出起始点到各个可达点的距离
		HarlanDijkstra test=new HarlanDijkstra(roads,enter);  
	    test.unweighted(enter);
		
		//得出到停车位的可达点的最短路径
		List<PathInfo> availableList = new ArrayList<>();
		for(Coordinate info:availableRoadTar){
			PathInfo pathInfo = test.getPathInfo(info.toString());
			availableList.add(pathInfo);
			
		}
		return availableList;
	}

	
	/**
	 * 获取通往所有目标的有效道路点(一个目标的临近道路点的集合)
	 * @param roads
	 * @param tragSet
	 * @return
	 */
	private static Set<Coordinate> getAllRoadNearTarg(Set<Coordinate> roads,Set<Coordinate> tragSet) {
		Set<Coordinate> allOfNearList = new HashSet<>();
		for (Coordinate targ : tragSet) {
//			System.out.println("getAllRoadNearTarg targ:"+targ);
			Set<Coordinate> childSet = getRoadNearTarg(roads,targ);
			allOfNearList.addAll(childSet);
		}
		return allOfNearList;
	}
	
	/**
	 * 获取通往一个目标的临近道路点
	 * 
	 * @param roads
	 * @param targ
	 * @return
	 */
	private static Set<Coordinate> getRoadNearTarg(Set<Coordinate> roads,Coordinate targ) {
		Set<Coordinate> nearList = new HashSet<>();
		Coordinate EAST = new Coordinate(targ.x + 1,targ.y);
		Coordinate SOUTH = new Coordinate(targ.x,targ.y + 1);
		Coordinate WEST = new Coordinate(targ.x - 1,targ.y);
		Coordinate NORTH = new Coordinate(targ.x,targ.y - 1);
		for (Coordinate info : roads) {
			if (EAST.equals(info)) {
				nearList.add(EAST);
			}
			if (SOUTH.equals(info)) {
				nearList.add(SOUTH);
			}
			if (WEST.equals(info)) {
				nearList.add(WEST);
			}
			if (NORTH.equals(info)) {
				nearList.add(NORTH);
			}
		}
		return nearList;
	}

}

在Main方法中，距离可达目标点(5,4)或(5,5)输出如下： 

nearest roads.size(): 49
nearest : [{"x":2,"y":0},{"x":2,"y":1},{"x":3,{"x":4,{"x":5,"y":2},"y":3}]

输出路径为json格式的，方便取用解析。


在Android中，改编贪食蛇的源码进行相关"地图"的随机生成。

经过各种检验，算法无误。

原文链接：https://www.f2er.com/javaschema/284653.html

猜你在找的设计模式相关文章

适配器模式-让不兼容的接口得以适配
适配器模式将一个类的接口转换成客户期望的另一个接口，使得原本接口不兼容的类可以相互合...
策略模式-定义一个算法族
策略模式定义了一系列算法族，并封装在类中，它们之间可以互相替换，此模式让算法的变化独...
设计模式之高质量代码
设计模式讲的是如何编写可扩展、可维护、可读的高质量代码，它是针对软件开发中经常遇到的...
模板方法模式-封装一套算法流程
模板方法模式在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类中，使得子类可以在...
迭代器模式-统一集合的遍历方式
迭代器模式提供了一种方法，用于遍历集合对象中的元素，而又不暴露其内部的细节。
单例模式的五种实现方式及优缺点
单例模式（Singleton Design Pattern）保证一个类只能有一个实例，并提供一个全局访问点。
组合模式-统一的处理个别对象与组合对象
组合模式可以将对象组合成树形结构来表示“整体-部分”的层次结构，使得客户可以用一致的方...
装饰者模式-动态的包装原有对象的行为
装饰者模式能够更灵活的，动态的给对象添加其它功能，而不需要修改任何现有的底层代码。
观察者模式-将消息通知给观察者
观察者模式（Observer Design Pattern）定义了对象之间的一对多依赖，当对象状态改变的时候...
代理模式-访问对象的代理而非其本身
代理模式为对象提供一个代理，来控制对该对象的访问。代理模式在不改变原始类代码的情况下...
算法设计模式多媒体技术正则表达式ElasticsearchFlinkHadoopIDE
受约束摘*day25Java常用类库置信lamda留存持续录入年后正则表达式303.17regularexpre匹多模适20130322基础理论pathmunge涵义reectok需要转义的特资源分享validationex简明魔法里弄形如源码实现完备actionscript