前言

最新更新了github。欢迎多评论+讨论，共同努力。
往后准备更新大数据和微服务的BLOG

由于项目需要计算两个地铁站之前最短距离及其线路流程。

引发使用迪杰斯特拉算法计算带权值两点之前最短距离。

网上资料多用的是C++写的算法，在这里用的是Java。实现的方法可以有很多，重要的是把原理理解后用清晰的代码实现。

这里参考了网上的资料：https://blog.csdn.net/wangchsh2008/article/details/46288967
发现类的职责不十分明确并且逻辑稍微混乱进行了改进。并且加入真实距离后会产生BUG

Github

地址：https://github.com/ithuhui/hui-core-algorithm-dijkstra
分支：master
位置：com.hui.algorithm.app.DijkstraApp

算法原理

算法原理我相信搜索能搜出一大把，我提出较为重要的点并辅以代码展示

1. 寻找分析点的所有相邻点并记录权值
2. 选取最短距离的邻点B
3. 循环遍历所有

类职责划分

DataBuilder 数据初始化 （相邻点之间距离）（实际中根据情况用TXT或者数据库读取初始化数据）

Result 运行结果

Station 站点信息

Code

Station&Result&DataBuilder

private static HashMap<station> resultMap = new HashMap<>();//结果集

private static List<station> analysisList = new ArrayList<>();//分析过的站点

 /**
* <b><code>Station</code></b>
* <p/>
* Description:
* <p/>
* <b>Creation Time:</b> 2018/7/19 16:40.
*
* @author huweihui
* @since metrodev2 0.1.0
*/
public class Station {
private String name;
private String line;
private List<Station> linkStations = new ArrayList<>();
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getLine() {
return line;
}
public void setLine(String line) {
this.line = line;
}
public List<Station> getLinkStations() {
return linkStations;
}
public void setLinkStations(List<Station> linkStations) {
this.linkStations = linkStations;
}
public Station(String name, String line) {
this.name = name;
this.line = line;
}
public Station(String name) {
this.name = name;
}
public Station (){
}
@Override
public boolean equals(Object obj) {
if(this == obj){
return true;
} else if(obj instanceof Station){
Station s = (Station) obj;
if(s.getName().equals(this.getName())){
return true;
} else {
return false;
}
} else {
return false;
}
}
@Override
public int hashCode() {
return this.getName().hashCode();
}
@Override
public String toString() {
return "Station{" +
"name='" + name + ''' +
", line='" + line + ''' +
", linkStations=" + linkStations +
'}';
}
}

/**
* <b><code>Result</code></b>
* <p/>
* Description:
* <p/>
* <b>Creation Time:</b> 2018/7/24 14:56.
*
* @author huweihui
* @since metrodev2 0.1.0
*/
public class Result {
private Station star;
private Station end;
private Double distance = 0.0D;
private List<Station> passStations = new ArrayList<>();
public Station getStar() {
return star;
}
public void setStar(Station star) {
this.star = star;
}
public Station getEnd() {
return end;
}
public void setEnd(Station end) {
this.end = end;
}
public Double getDistance() {
return distance;
}
public void setDistance(Double distance) {
this.distance = distance;
}
public List<Station> getPassStations() {
return passStations;
}
public void setPassStations(List<Station> passStations) {
this.passStations = passStations;
}
public Result(Station star, Station end, Double distance) {
this.star = star;
this.end = end;
this.distance = distance;
}
public Result(){
}
@Override
public String toString() {
return "Result{" +
"star=" + star +
", end=" + end +
", distance=" + distance +
", passStations=" + passStations +
'}';
}
}

/**
* <b><code>com.richstonedt.metro.app.DataBuilder</code></b>
* <p/>
* Description:
* <p/>
* <b>Creation Time:</b> 2018/7/10 12:36.
*
* @author huweihui
* @since metro-dev 0.1.0
*/
public class DataBuilder {
public static List<Station> line1 = new ArrayList<Station>();
public static List<Station> line2 = new ArrayList<Station>();
public static List<Station> line3 = new ArrayList<Station>();
public static List<Station> line3N = new ArrayList<Station>();
public static List<Station> line4 = new ArrayList<Station>();
public static List<Station> line5 = new ArrayList<Station>();
public static List<Station> line6 = new ArrayList<Station>();
public static List<Station> line7 = new ArrayList<Station>();
public static List<Station> line8 = new ArrayList<Station>();
public static List<Station> line9 = new ArrayList<Station>();
public static List<Station> line13 = new ArrayList<Station>();
public static List<Station> line14 = new ArrayList<Station>();
public static List<Station> lineAPM = new ArrayList<Station>();//APM
public static List<Station> lineGF = new ArrayList<Station>();//广佛线
public static LinkedHashSet<List<Station>> lineSet = new LinkedHashSet<>();//所有线集合
public static int totalStaion = 0;//总的站点数量
private DataBuilder(){
}
public static void init (String lineStr,List<Station> line,String lineName){
}
private static void getLine(String lineStr,List<Station> line,String lineName){
String[] lineArr = lineStr.split("，");
for (String s : lineArr) {
line.add(new Station(s,lineName));
}
}
static {
String line1Str = "西朗，坑口，花地湾，芳村，黄沙，长寿路，陈家祠，西门口，公园前，农讲所，烈士陵园，东山口，杨箕，体育西路，体育中心，广州东站";
String line2Str = "广州南站，石壁，会江，南浦，洛溪，南洲，东晓南，江泰路，昌岗，江南西，市二宫，海珠广场，公园前，纪念堂，越秀公园，广州火车站，三元里，飞翔公园，白云公园，白云文化广场，萧岗，江夏，黄边，嘉禾望岗";
String line3Str = "番禺广场，市桥，汉溪长隆，大石，厦滘，沥滘，大塘，客村，广州塔，珠江新城，体育西路，石牌桥，岗顶，华师，五山，天河客运站";
String line3NStr = "体育西路，林和西，广州东站，燕塘，梅花园，京溪南方医院，同和，永泰，白云大道北，嘉禾望岗，龙归，人和，高增，机场南，机场北";
String line4Str = "南沙客运港，南横，塘坑，大涌，广隆，飞沙角，金洲，蕉门，黄阁，黄阁汽车城，庆盛，东涌，低涌，海傍，石碁，新造，大学城南，大学城北，官洲，万胜围，车陂南，车陂，黄村";
String line5Str = "滘口，坦尾，中山八，西场，西村，广州火车站，小北，淘金，区庄，动物园，杨箕，五羊邨，珠江新城，猎德，潭村，员村，科韵路，车陂南，东圃，三溪，鱼珠，大沙地，大沙东，文冲";
String line6Str = "浔峰岗，横沙，沙贝，河沙，坦尾，如意坊，黄沙，文化公园，一德路，海珠广场，北京路，团一大广场，团一大广场，东湖，东山口，区庄，黄花岗，沙河顶，天平架，燕塘，天河客运站，长湴，植物园，龙洞，柯木塱，高塘石，黄陂，金峰，暹岗，苏元，萝岗，香雪";
String line7Str = "广州南站，石壁，谢村，钟村，汉溪长隆，南村万博，员岗，板桥，大学城南";
String line8Str = "凤凰新村，沙园，宝岗大道，昌岗，晓港，中大，鹭江，客村，赤岗，磨碟沙，新港东，琶洲，万胜围";
String line9Str = "飞鹅岭，花都汽车城，广州北站，花城路，花果山公园，花都广场，马鞍山公园，莲塘，清布，清塘，高增";
String line13Str = "鱼珠，裕丰围，双岗，南海神庙，夏园，南岗，沙村，白江，新塘，官湖，新沙";
String line14Str = "新和，红卫，新南，枫下，知识城，何棠下，旺村，汤村，镇龙北，镇龙";
String lineAPMStr = "广州塔，海心沙，大剧院，花城大道，妇儿中心，黄埔大道，天河南，体育中心南，林和西";
String lineGFStr = "新城东，东平，世纪莲，澜石，魁奇路，季华园，同济路，祖庙，普君北路，朝安，桂城，南桂路，礌岗，千灯湖，金融高新区，龙溪，菊树，西朗，鹤洞，沙涌，沙园，燕岗";
getLine(line1Str,line1,"line1");
getLine(line2Str,line2,"line2");
getLine(line3Str,line3,"line3");
getLine(line3NStr,line3N,"line3N");
getLine(line4Str,line4,"line4");
getLine(line5Str,line5,"line5");
getLine(line6Str,line6,"line6");
getLine(line7Str,line7,"line7");
getLine(line8Str,line8,"line8");
getLine(line9Str,line9,"line9");
getLine(line13Str,line13,"line13");
getLine(line14Str,line14,"line14");
getLine(lineAPMStr,lineAPM,"lineAPM");
getLine(lineGFStr,lineGF,"lineGF");
lineSet.add(line1);
lineSet.add(line2);
lineSet.add(line3);
lineSet.add(line3N);
lineSet.add(line4);
lineSet.add(line5);
lineSet.add(line6);
lineSet.add(line7);
lineSet.add(line8);
lineSet.add(line9);
lineSet.add(line13);
lineSet.add(line14);
lineSet.add(lineAPM);
lineSet.add(lineGF);
totalStaion = line1.size() + line2.size() + line3.size() + line4.size() + line5.size() + line6.size()
+ line7.size()+line8.size()+line9.size()+line13.size()+line14.size()+lineAPM.size()+lineGF.size();
System.out.println("总的站点数量：" + totalStaion);
}
}

算法

对应上面算法最关键的三点

1. 找所有相邻点

private static List<Station> getLinkStations(Station station) {
List<Station> linkedStaions = new ArrayList<Station>();
for (List<Station> line : SZDataBuilder.lineSet) {
for (int i = 0; i < line.size() ; i++) {
if (station.equals(line.get(i))) {
if (i == 0) {
linkedStaions.add(line.get(i + 1));
} else if (i == (line.size()-1) ) {
linkedStaions.add(line.get(i - 1));
}else {
linkedStaions.add(line.get(i+1));
linkedStaions.add(line.get(i-1));
}
}
}
}
return linkedStaions;
}

2. 计算最小权值并找出下一个需要分析的点

//通过计算最小权值 计算下一个需要分析的点
private static Station getNextStation() {
Double min = Double.MAX_VALUE;
Station rets = null;
Set<Station> stations = resultMap.keySet();
for (Station station : stations) {
if (analysisList.contains(station)) {
continue;
}
Result result = resultMap.get(station);
if (result.getDistance() < min) {
min = result.getDistance();
rets = result.getEnd();
}
}
return rets;
}

3. 循环遍历后获取结果

   public static Result calculate(Station star, Station end) {
   if (!analysisList.contains(star)) {
   analysisList.add(star);
   }
   if (star.equals(end)){
   Result result = new Result();
   result.setDistance(0.0D);
   result.setEnd(star);
   result.setStar(star);
   resultMap.put(star, result);
   return resultMap.get(star);
   }
   if (resultMap.isEmpty()) {
   List<Station> linkStations = getLinkStations(star);
   for (Station station : linkStations) {
   Result result = new Result();
   result.setStar(star);
   result.setEnd(station);
   String key = star.getName() + ":" + station.getName();
   Double distance = DistanceBuilder.getDistance(key);
   result.setDistance(distance);
   result.getPassStations().add(station);
   resultMap.put(station, result);
   }
   }
   Station parent = getNextStation();
   if (parent==null){
   Result result = new Result();
   result.setDistance(0.0D);
   result.setStar(star);
   result.setEnd(end);
   return resultMap.put(end, result);
   }
   if (parent.equals(end)) {
   return resultMap.get(parent);
   }
   List<Station> childLinkStations = getLinkStations(parent);
   for (Station child : childLinkStations) {
   if (analysisList.contains(child)) {
   continue;
   }
   String key = parent.getName() + ":" + child.getName();
   Double distance = DistanceBuilder.getDistance(key);
   if( parent.getName().equals(child.getName())){
   distance = 0.0D;
   }
   Double parentDistance = resultMap.get(parent).getDistance();
   distance = doubleAdd(distance, parentDistance);
   List<Station> parentPassStations = resultMap.get(parent).getPassStations();
   Result childResult = resultMap.get(child);
   if (childResult!=null){
   if (childResult.getDistance() > distance) {
   childResult.setDistance(distance);
   childResult.getPassStations().clear();
   childResult.getPassStations().addAll(parentPassStations);
   childResult.getPassStations().add(child);
   }
   }else {
   childResult = new Result();
   childResult.setDistance(distance);
   childResult.setStar(star);
   childResult.setEnd(child);
   childResult.getPassStations().addAll(parentPassStations);
   childResult.getPassStations().add(child);
   }
   resultMap.put(child, childResult);
   }
   analysisList.add(parent);
   calculate(star, end);
   return resultMap.get(end);
   }
   

应用场景

最短距离算法~~~ 算最短距离的时候用的。

当时项目是计算地铁最优乘坐方式。小项目，就不把拥挤和换线时间加入最优因素了哈。

总结

算法很简单，但是很多时候遇到新东西，大多数是基于巨人的肩膀进行修修改改，所以当时也是看了那位朋友的代码，他把所有的距离都当做1进行距离计算，实际就是最短步数是一样的。思想不难，并且把相邻站点的真实距离算进去后感觉有某些BUG。代码结构有点混乱，因此进行了一些修改。

作者

 作者：HuHui
转载：欢迎一起讨论web和大数据问题,转载请注明作者和原文链接，感谢

最后

以上就是魁梧大树为你收集整理的迪杰斯特拉（dijkstra）-两个地铁站最短距离前言Github算法原理类职责划分Code应用场景总结作者的全部内容，希望文章能够帮你解决迪杰斯特拉（dijkstra）-两个地铁站最短距离前言Github算法原理类职责划分Code应用场景总结作者所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。