navigation.java
来自「自己上学编的基于Dijkstra的最短路径&最大流量java源码」· Java 代码 · 共 693 行 · 第 1/2 页
JAVA
693 行
}
}
}
}
}
}
// insert node in selected vertices
String node = mp.getLastNode();
groupA.add(node);
/*
* if because of inserting new point, lead to decrease minimum weight in not_selected vertices,reset minimum weight
*/
setWeight_FT(node);
}
}
return output;
}
/**
* Finds the shortest distance in kilometers between A and B
* using the Dijkstra algorithm.
*
* @param A the start point A
* @param B the destination point B
* @return the shortest distance in kilometers rounded upwards.
* SOURCE_NOT_FOUND if point A is not on the map
* DESTINATION_NOT_FOUND if point B is not on the map
* SOURCE_DESTINATION_NOT_FOUND if point A and point B are not on the map
* NO_PATH if no path can be found between point A and point B
*/
public int findShortestDistance(String A, String B) {
if(!findNodeinRoads(A) && !findNodeinRoads(B))
return SOURCE_DESTINATION_NOT_FOUND;
else if(!findNodeinRoads(A))
return SOURCE_NOT_FOUND;
else if(!findNodeinRoads(B))
return DESTINATION_NOT_FOUND;
else {
this.findShortestRoute(A, B);
int sd = this.shortestDistance;
if (sd == -1)
return NO_PATH;
else
return sd;
}
}
/**
* Find the fastest route between A and B using
* the Dijkstra algorithm.
*
* @param A Source
* @param B Destination
* @return the fastest time in minutes rounded upwards.
* SOURCE_NOT_FOUND if point A is not on the map
* DESTINATION_NOT_FOUND if point B is not on the map
* SOURCE_DESTINATION_NOT_FOUND if point A and point B are not on the map
* NO_PATH if no path can be found between point A and point B
*/
public int findFastestTime(String A, String B) {
if(!findNodeinRoads(A) && !findNodeinRoads(B))
return SOURCE_DESTINATION_NOT_FOUND;
else if(!findNodeinRoads(A))
return SOURCE_NOT_FOUND;
else if(!findNodeinRoads(B))
return DESTINATION_NOT_FOUND;
else {
this.findFastestRoute(A, B);
float ft = this.fastestTime;
if (ft == -1)
return NO_PATH;
else
return (int)Math.ceil(ft);
}
}
/**
* test a vertex in the map or not
*
* @param name String
* @return true if the vertex in the map
* false otherwise
*/
private boolean findNodeinRoads(String name) {
for(Kante ro : roads) {
if(ro.getPreNode().equals(name) || ro.getNachNode().equals(name))
return true;
}
return false;
}
/**
* find a vertex with given name in the vertices collection
*
* @param name String
* @return null if the vertex is not exist in the vertices collection
* vertex be found otherwise
*/
private Knote findNodeinNodes(String name) {
for(Knote no : nodes) {
if(no.getName().equals(name))
return no;
}
System.out.println("Node can not be found!" );
return null;
}
/**
* find a vertex from not_selected vertices to which there is a minimal edge
* between selected vertices and not_selected vertices by finding shortest distance
*
* @return a MiniPass which represents the shortest (and/or) path and weight between points on a map
*/
private MiniPass getMinSideNode_SD() {
MiniPass minMsp = null;
if (groupB.size() > 0) {
String stemp = null;
for (String s : groupB) {
MiniPass msp = getMinPath_SD(s);
if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) {
minMsp = msp;
stemp = s;
}
}
if(stemp != null)
groupB.remove(stemp);
}
return minMsp;
}
/**
* find a vertex from not_selected vertices to which there is a minimal edge
* between selected vertices and not_selected vertices by finding fastest time
*
* @return a MiniPass which represents the shortest (and/or) path and weight between points on a map
*/
private MiniPass getMinSideNode_FT() {
MiniPass minMsp = null;
if (groupB.size() > 0) {
String stemp = null;
for (String s : groupB) {
MiniPass msp = getMinPath_FT(s);
if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) {
minMsp = msp;
stemp = s;
}
}
if(stemp != null)
groupB.remove(stemp);
}
return minMsp;
}
/**
* to get a shortest (and/or) path of the given vertex by finding shortest distance
*
* @param nodename String
* @return a MiniPass which represents the shortest (and/or) path and weight between the given points and source
*/
private MiniPass getMinPath_SD(String nodename) {
MiniPass msp = new MiniPass(nodename);
if (results != null && groupA != null) {
for (String s : groupA) {
MiniPass tempMsp = new MiniPass(nodename);
String parent = s;
String curNode = nodename;
while (parent != null) {
int weight = getWeight_SD(parent, curNode);
if (weight > -1 && parent != curNode) {
tempMsp.addNode(parent);
tempMsp.addWeight(weight);
curNode = parent;
parent = getParent(parent);
}
else
break;
}
if (msp.getWeight() == -1 || tempMsp.getWeight()!=-1 && msp.getWeight() > tempMsp.getWeight())
msp = tempMsp;
}
}
return msp;
}
/**
* to get a shortest (and/or) path of the given vertex by finding fastest time
*
* @param nodename String
* @return a MiniPass which represents the shortest (and/or) path and weight between the given points and source
*/
private MiniPass getMinPath_FT(String nodename) {
MiniPass msp = new MiniPass(nodename);
if (results != null && groupA != null) {
for (String s : groupA) {
MiniPass tempMsp = new MiniPass(nodename);
String parent = s;
String curNode = nodename;
while (parent != null) {
float weight = getWeight_FT(parent, curNode);
if (weight > -1 && parent != curNode) {
// get wait time into counting
if(!parent.equals(this.startNode))
weight += findNodeinNodes(parent).getWaitTime();
tempMsp.addNode(parent);
tempMsp.addWeight(weight);
curNode = parent;
parent = getParent(parent);
}
else
break;
}
if (msp.getWeight() == -1 || tempMsp.getWeight()!=-1 && msp.getWeight() > tempMsp.getWeight())
msp = tempMsp;
}
}
return msp;
}
/**
* to get a PreNode of a vertex in the shortest path
*
* @param nodename String
* @return the PreNode if PreNode is found
* null otherwise
*/
private String getParent(String nodename) {
if (results != null) {
for (Result s : results) {
if (s.getNachNode() == nodename) {
return s.getPreNode();
}
}
}
return null;
}
/**
* to get weight between two vertices from edges collections by finding shortest distance
*
* @param preNode String
* @param nachNode String
* @return the weight if a edge between given nodes is exist
* -1 otherwise
*/
private int getWeight_SD(String preNode, String nachNode) {
if (roads != null) {
for (Kante ro : roads) {
if (ro.getPreNode().equals(preNode) && ro.getNachNode().equals(nachNode))
return ro.getLang();
}
}
return -1;
}
/**
* to get weight between two vertices from edges collections by finding fastest time
*
* @param preNode String
* @param nachNode String
* @return the weight if a edge between given nodes is exist
* -1 otherwise
*/
private float getWeight_FT(String preNode, String nachNode) {
if (roads != null) {
for (Kante ro : roads) {
if (ro.getPreNode().equals(preNode) && ro.getNachNode().equals(nachNode))
return ro.getRunTime();
}
}
return -1;
}
/**
* reset minimum weight in not_selected vertices by finding shortest distance
*
* @param preNode
*/
private void setWeight_SD(String preNode) {
if (roads != null && results != null && groupB != null) {
for (String s : groupB) {
MiniPass msp=getMinPath_SD(s);
float w1 = msp.getWeight();
if (w1 == -1)
continue;
for (Result r : results) {
if (r.getNachNode() == s) {
if (r.getWeight() == -1 || r.getWeight() > w1) {
r.setWeight(w1);
//reset preNode in the shortest path
r.setPreNode(preNode);
break;
}
}
}
}
}
}
/**
* reset minimum weight in not_selected vertices by finding fastest time
*
* @param preNode
*/
private void setWeight_FT(String preNode) {
if (roads != null && results != null && groupB != null) {
for (String s : groupB) {
MiniPass msp=getMinPath_FT(s);
float w1 = msp.getWeight();
if (w1 == -1)
continue;
for (Result r : results) {
if (r.getNachNode() == s) {
if (r.getWeight() == -1 || r.getWeight() > w1) {
r.setWeight(w1);
//reset preNode in the shortest path
r.setPreNode(preNode);
break;
}
}
}
}
}
}
}
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?