package org.test;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Optional;
import java.util.Random;
public class MyDijkstra
{
private final int m_max = Integer.MAX_VALUE;
private int m_total;
private int[][] m_matirx;
private int[] m_mark;
private Map<String,Map<String,Integer>> m_line;
private Map<String,Integer> m_nodesPos = new HashMap<String,Integer>();
/**
*
* @param nodes 所有的顶点
* @param line 所有直接相连顶点间的距离(双向)
*/
public MyDijkstra(String[] nodes,Map<String,Map<String,Integer>> line)
{
this.m_total = nodes.length;
m_matirx = new int[this.m_total][this.m_total];
m_mark = new int[m_total];
for(int i = 0; i < m_total; i++)
{
for(int j = 0; j < m_total; j++)
{
if (i == j)
{
m_matirx[i][j] = 0;
}
else
{
m_matirx[i][j] = m_max;
}
}
m_nodesPos.put(nodes[i], i);
}
line.forEach((id1,lines)->{
lines.forEach((id2,length)->{
m_matirx[m_nodesPos.get(id1)][m_nodesPos.get(id2)] = length;
});
});
m_line = line;
}
private void printMatirx()
{
for (int i = 0; i < m_total; i++)
{
for(int j = 0; j < m_total; j++)
{
if (this.m_matirx[i][j] == this.m_max)
{
System.out.print(" ∞ " + "-");
}
else
{
System.out.print(String.format("d", this.m_matirx[i][j]) + "-");
}
}
System.out.print("\n");
}
}
private String getShortestDirectlyConnected(String s,String e) throws Exception
{
int minLength = this.m_max;
String ret = null;
for(String p1 : m_line.keySet())
{
if (p1.equals(e))
{
Map<String,Integer> line1 = m_line.get(p1);
for(String p2 : line1.keySet())
{
int length = this.m_matirx[this.m_nodesPos.get(s)][this.m_nodesPos.get(p2)] + this.m_line.get(e).get(p2);
if (length < minLength)
{
minLength = length;
ret = p2;
}
}
return ret;
}
}
throw new Exception("imposiable");
}
private LinkedList<String> getShortestRoadLine(String s,String e)
{
LinkedList<String> ret = new LinkedList<String>();
if (s.equals(e))
{
return ret;
}
String end = e;
ret.add(e);
try
{
while(true)
{
String mid = getShortestDirectlyConnected(s,end);
ret.add(mid);
//System.out.println("------->" + s + "," + end + "," + mid);
if (mid.equals(s))
{
Collections.reverse(ret);
return ret;
}
end = mid;
}
}
catch (Exception ex)
{
return ret;
}
}
public Optional <LinkedList<String>> getShortestRoad(String str,String etr)
{
int s = this.m_nodesPos.get(str);
int e = this.m_nodesPos.get(etr);
int [] dis = new int[m_total];
for(int i = 0; i < this.m_total; i++)
{
m_mark[i] = 0;
dis[i] = this.m_matirx[s][i];
}
dis[s] = 0;
this.m_mark[s] = 1;
int min = -1;
int k = -1;
for(int i = 0; i < this.m_total; i++)
{
min = this.m_max;
for(int j = 0; j < this.m_total; j++)
{
if (this.m_mark[j] == 0 && dis[j] < min)
{
min = dis[j];
k = j;
}
}
//取出了下一个距离s路径最近的点,可能s直接是孤立点
if (k == -1)
{
return Optional.ofNullable(null);
}
this.m_mark[k] = 1;
//修正以前的结果（j到原点的距离可能随着新的k距离的更新有更短的路径出现,所以要更新j到s的路径长度）
for(int j = 0; j < this.m_total; j++)
{
if (this.m_mark[j] == 0 && (this.m_matirx[k][j] + dis[k]) > 0 && (this.m_matirx[k][j] + dis[k]) < dis[j])
{
dis[j] = this.m_matirx[k][j] + dis[k];
this.m_matirx[s][j] = dis[j];
}
}
}
if (dis[e] == this.m_max)
{
return Optional.ofNullable(null);
}
//this.printMatirx();
return Optional.of(getShortestRoadLine(str,etr));
}
public static void main(String[] args)
{
String[] points = {"1","2","3","4","5","6","7","8","9"};
Map<String,Map<String,Integer>> line = new HashMap<String,Map<String,Integer>>();
line.put("1", new HashMap<String,Integer>());
line.get("1").put("2", 4);
line.get("1").put("4", 2);
line.get("1").put("3", 5);
line.put("2", new HashMap<String,Integer>());
line.get("2").put("1", 4);
line.get("2").put("5", 3);
line.put("3", new HashMap<String,Integer>());
line.get("3").put("1", 5);
line.get("3").put("6", 7);
line.put("4", new HashMap<String,Integer>());
line.get("4").put("7", 5);
line.get("4").put("1", 2);
line.put("5", new HashMap<String,Integer>());
line.get("5").put("2", 3);
line.get("5").put("7", 9);
line.get("5").put("8", 4);
line.put("6", new HashMap<String,Integer>());
line.get("6").put("3", 7);
line.get("6").put("7", 1);
line.put("7", new HashMap<String,Integer>());
line.get("7").put("6", 1);
line.get("7").put("5", 9);
line.get("7").put("4", 5);
line.put("8", new HashMap<String,Integer>());
line.get("8").put("5", 4);
line.get("8").put("9", 3);
line.put("9", new HashMap<String,Integer>());
line.get("9").put("8", 3);
MyDijkstra o = new MyDijkstra(points,line);
Optional <LinkedList<String>> road = o.getShortestRoad("1","6");
if (road.isPresent())
{
System.out.println("road--->" + road.get());
}
else
{
System.out.println("can not find road");
}
}
//模拟矩阵块的最短寻路
// public static void main(String[] args)
// {
// int width = 50;
// int height = 50;
// int startX = 0;
// int startY = 0;
// int endX = 45;
// int endY = 48;
// int[][] rect = new int[width][height];
// for(int i = 0; i < width; i++)
// {
// for(int j = 0; j < height ; j++)
// {
// rect[i][j] = 1;
// }
// }
//
// rect[startX][startY] = 2;//起点
// rect[endX][endY] = 3;//终点
// Random r1 = new Random(System.currentTimeMillis());
//
// //障碍,不能通过
// for(int i = 0; i < 500; i++)
// {
// int randX = Math.abs(r1.nextInt() % width);
// int randY = Math.abs(r1.nextInt() % height);
// if (rect[randX][randY] == 1)
// {
// rect[randX][randY] = 4;
// }
// }
//
// LinkedHashMap<String,int[]> listMap = new LinkedHashMap<String,int[]>();
// int pos = 0;
//
// for(int i = 0; i < width;i++)
// {
// for (int j = 0; j < height;j++)
// {
// if (rect[i][j] != 4)
// {
// listMap.put(i + "_" + j, new int[]{i,j,pos++});
// }
// }
// }
//
// Map<String,Map<String,Integer>> line = new HashMap<String,Map<String,Integer>>();
//
// listMap.forEach((id,node)->{
// line.put(id, new HashMap<String,Integer>());
// String id1 = node[0] + "_" + (node[1] + 1);
// String id2 = node[0] + "_" + (node[1] - 1);
// String id3 = (node[0] + 1) + "_" + node[1];
// String id4 = (node[0] - 1) + "_" + node[1];
// if (listMap.containsKey(id1))
// {
// line.get(id).put(id1, 1);
// }
// if (listMap.containsKey(id2))
// {
// line.get(id).put(id2, 1);
// }
// if (listMap.containsKey(id3))
// {
// line.get(id).put(id3, 1);
// }
// if (listMap.containsKey(id4))
// {
// line.get(id).put(id4, 1);
// }
// });
//
// String[] node = new String[listMap.size()];
//
// pos = 0;
//
// for(Entry<String,int[]> entry : listMap.entrySet())
// {
// node[pos++] = entry.getKey();
// }
//
// MyDijkstra o = new MyDijkstra(node,line);
// Optional <LinkedList<String>> road = o.getShortestRoad(startX + "_" + startY,endX + "_" + endY);
// if (!road.isPresent())
// {
// System.out.println("can not find shortest road");
// return;
// }
// road.get().forEach(p->{
// int[] mapP = listMap.get(p);
// if (rect[mapP[0]][mapP[1]] == 1)
// {
// rect[mapP[0]][mapP[1]] = 0;
// }
// });
// for(int i = 0; i < width;i++)
// {
// for (int j = 0; j < height;j++)
// {
// System.out.print(rect[i][j] + " ");
// }
// System.out.print("\n");
// }
// }
}
转载请注明原文地址: https://ju.6miu.com/read-1000185.html
