基于无向图且权重单一的最短路径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

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