package com.demo.navtogether.utils;
|
|
import android.graphics.Point;
|
|
import java.util.ArrayList;
|
import java.util.HashMap;
|
import java.util.Map;
|
import java.util.TreeMap;
|
|
/**
|
* My father is Object, ites purpose of 迪杰斯特拉算法
|
*
|
* @purpose Created by Runt (qingingrunt2010@qq.com) on 2020-12-23.
|
*/
|
|
public class DijkstraUtils {
|
|
HashMap<PathPlan.Place, PathPlan.Distance> distances;//每个点的信息集合
|
|
public DijkstraUtils(HashMap<PathPlan.Place, PathPlan.Distance> distances) {
|
this.distances = distances;
|
}
|
|
|
public ArrayList<PathPlan.Place> excute(PathPlan.Place start ){
|
return excute(start,null);
|
}
|
|
/**
|
* 执行算法
|
* @param start 起点
|
* @param end
|
*/
|
public ArrayList<PathPlan.Place> excute(PathPlan.Place start, PathPlan.Place end){
|
|
PathPlan.Distance startDis = distances.get(start);
|
PathPlan.Distance endDis = end == null ? null:distances.get(end);
|
deletePlace(start);
|
if(end != null){//如果有终点则去除
|
deletePlace(end);
|
}
|
ArrayList<PathPlan.Place> places = new ArrayList<>();
|
places.add(start);
|
while (distances.size()>0){//循环遍历
|
PathPlan.Place nearWay = findNearWay(startDis);//获取与其他点的最短个那一个
|
startDis = distances.get(nearWay);//距离信息
|
deletePlace(nearWay);//从集合中删除，避免下次循环再次出现该地点
|
places.add(nearWay);//添加到线路集合记录中
|
}
|
if(end != null){//如果有终点则最后追加
|
end.distance = endDis.distanceMap.get(places.get(places.size()-1));
|
places.add(end);
|
}
|
return places;//返回规划的路线集合
|
|
}
|
|
/**
|
* 清除位置
|
* @param place
|
*/
|
private void deletePlace(PathPlan.Place place){
|
distances.remove(place);
|
for(PathPlan.Place p : distances.keySet()){//将与之相关的距离也清除
|
distances.get(p).distanceMap.remove(place);
|
}
|
}
|
|
/**
|
* 寻找最近的位置
|
* @return
|
*/
|
public PathPlan.Place findNearWay(PathPlan.Distance distance){
|
PathPlan.Place place = null;
|
double dist = -1;
|
for(PathPlan.Place temp : distance.distanceMap.keySet()){//循环遍历
|
double placeDist = distance.distanceMap.get(temp);//对应位置距离；
|
placeDist = placeDist - placeDist*temp.priority/100;//计算权重
|
if(dist == -1){
|
dist = placeDist;
|
temp.distance = dist;
|
place = temp;
|
}else if( dist > placeDist){//若小于之前对比的数据
|
dist = placeDist;
|
temp.distance = dist;
|
place = temp;
|
}
|
}
|
return place;
|
}
|
|
|
public static void main(String[] args) {
|
|
ArrayList<PathPlan.Place> places = new ArrayList<>();
|
places.add(new PathPlan.Place("A",random(),0));
|
places.add(new PathPlan.Place("B",random(),0));
|
places.add(new PathPlan.Place("C",random(),0));
|
places.add(new PathPlan.Place("D",random(),0));
|
places.add(new PathPlan.Place("E",random(),0));
|
places.add(new PathPlan.Place("F",random(),0));
|
Map map = new HashMap();
|
map.put(places.get(2),"hehe");
|
System.out.println("2"+map.get(places.get(2)));
|
ArrayList<PathPlan.Place> excute = new DijkstraUtils(PathPlan.intPoints(places)).excute(places.get(2));
|
for(int i = 0 ; i < excute.size() ; i ++){
|
System.out.println(excute.get(i)+" 距离："+(i == excute.size() -1?"":TriangleUtils.getLengthOfSide(excute.get(i).point,excute.get(i+1).point)) +" "+excute.get(i).distance);
|
}
|
|
|
}
|
|
ArrayList<ArrayList<PathPlan.Place>> arrayLists = new ArrayList<>();//路线记录
|
/**
|
* 自定义规划路线算法
|
* @param start 起始地点
|
* @param end 末尾地点
|
*/
|
public ArrayList<ArrayList<PathPlan.Place>> initCustomPathPlan( PathPlan.Place start,PathPlan.Place end){
|
arrayLists.clear();//清空记录
|
ArrayList<PathPlan.Place > places = new ArrayList<>(distances.keySet());//所有地点集合
|
for(int i=1;i<=places.size();i++){
|
sortPlace(places,new ArrayList<PathPlan.Place>(),i,start,end);
|
}
|
return arrayLists;
|
|
}
|
//最短距离
|
double dist = -1;
|
|
/**
|
* 组合
|
* @param datas 地点数据
|
* @param target 整理的新路线
|
* @param num 循环的下标位置，即路线规划的地点数量
|
* @param start 起始地点
|
* @param end 末尾地点
|
*/
|
private void sortPlace(ArrayList<PathPlan.Place> datas, ArrayList<PathPlan.Place> target,int num,PathPlan.Place start,PathPlan.Place end) {
|
if (target.size() == num) {
|
ArrayList newDatas = new ArrayList( );
|
ArrayList<PathPlan.Place > places = new ArrayList<>(distances.keySet());//所有地点集合
|
//数量不够，起始和末尾不对应，则不再执行
|
if(places.size()> num || start!=null && !target.get(0).equals(start) || end!=null && !target.get(target.size()-1).equals(end)){
|
return;
|
}
|
double tempDist = 0 ;
|
for (PathPlan.Place obj : target) {
|
//复制对象
|
PathPlan.Place place = new PathPlan.Place(obj);
|
//距离
|
place.distance = newDatas.size() == 0 ?0: distances.get(obj).distanceMap.get(newDatas.get(newDatas.size() - 1));
|
tempDist+=place.distance;
|
newDatas.add(place);
|
}
|
//记录最短距离
|
if(dist == -1 || dist >= tempDist){
|
if(dist > tempDist){
|
arrayLists.clear();//清除之前的数据
|
}
|
dist = tempDist;
|
arrayLists.add(newDatas);
|
}else if(dist < tempDist){ //当前距离不是最短
|
return;
|
}
|
return;
|
}
|
for (int i = 0; i < datas.size(); i++) {
|
ArrayList newDatas = new ArrayList(datas);
|
ArrayList newTarget = new ArrayList(target);
|
newTarget.add(newDatas.get(i));
|
newDatas.remove(i);
|
sortPlace(newDatas, newTarget,num,start,end);
|
}
|
}
|
|
/**
|
* 创建一个随机位置 坐标在0-100内
|
* @return
|
*/
|
public static Point random(){
|
Point point = new Point();
|
|
point.x = (int) (Math.random()*100);
|
point.y = (int) (Math.random()*100);
|
|
return point;
|
}
|
|
}
|
