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

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

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

首先参考了博友JavaMan_chen的博文

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

算法中，如果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;}@Overridepublic 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;}@Overridepublic int hashCode() {return x*10000+y;}/** * 以JSON格式展示坐标 */@Overridepublic String toString() {return "{\&;x\&;:" + x + ",\&;y\&;:" + y + "}";}}并定义了路径数据结构

PathInfo.java

package com.harlan.dijkstra;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;}}

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

/** * 和周围的四个点建立关系 * * @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;}无权最短路径的算法如下:// 无权最短路径计算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);}}}}遍历获取实际最短路径private List<Coordinate> getPath(Coordinate dest, List<Coordinate> cdList) {if (dest.lastPoint != null) {cdList = (getPath(dest.lastPoint, cdList));}cdList.add(dest);return cdList;}显示最短路径:// 显示一条路径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或者其他地方使用了世上没有绝望的处境，只有对处境绝望的人。

相关文章：

你感兴趣的文章：

标签云：