У меня есть вершина, которую я пытаюсь достичь, называемая пунктом назначения. В настоящее время мой алгоритм, кажется, проходит эту вершину.
Кажется, что всегда добавляется последнее ребро, которое будет проверено на кратчайшее расстояние. Я не уверен, связано ли это с ошибкой в моем алгоритме или с тем, как я добавляю соседей, но я пытался проверить оба.
Иногда добавляются последние 2 ребра, например:
ID: 39330 Значение: 1.309999942779541
ID: 39360 Значение: 1.940000057220459
ID: 39374 Значение: 1.9700000286102295
Добавлено: 39360 Добавлено: 39374
Или добавлен только последний:
ID: 39347 Значение: 1.2999999523162842
ID: 24955 Значение: 2.5799999237060547
Добавлено: 24955
Любые мысли, рекомендации или идеи очень ценятся!
График
class Graph {
private final Set<Vertex> vertices = new HashSet<Vertex>();
private final Set<Edge> edges = new HashSet<Edge>();
public void addVertex(int id, String name) {
Vertex vertex = new Vertex(id,name);
vertices.add(vertex);
//System.out.println("ID:" + vertex.getID() + "Name:" + vertex.getName());
}
public void addEdge(double weight, Vertex vertex1, Vertex vertex2, String extra) {
Edge edge = new Edge(weight,vertex1,vertex2,extra);
edges.add(edge);
}
public void printVertices() {
for(Vertex vertex : vertices){
System.out.println("ID:" + vertex.getID() + " Name:" + vertex.getName());
}
}
public void printEdges() {
for(Edge edge : edges){
System.out.println("StartVertex:" + edge.getStartVertex() + "ID: "+ edge.getStartVertex().getID() +" EndVertex:" + edge.getTargetVertex()+"ID: "+ edge.getTargetVertex().getID() + "Weight:" + edge.getWeight());
}
}
public Vertex getVertex(Vertex v) {
return v;
}
public Map<Vertex, Double> getNeighbours(Vertex vertex) {
Map<Vertex,Double> neighbors = new HashMap();
Object[] check = edges.toArray();
Object[] check2 = vertices.toArray();
for(int i = 0; i < edges.size(); i++) {
if(((Edge) check[i]).getStartVertex().getID() == vertex.getID()) {
neighbors.put(((Edge) check[i]).getTargetVertex(),((Edge) check[i]).getWeight());
}
//check for
/*else if(((Edge) check[i]).getTargetVertex() == vertex) {
neighbors.put(((Edge) check[i]).getStartVertex(),((Edge) check[i]).getWeight());
}*/
}
for (Entry<Vertex, Double> entry : neighbors.entrySet()) {
System.out.println("ID: " + entry.getKey().getID() + " Value: " + entry.getValue() );
}
return neighbors;
}
}
ShortestPathFinder
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Set;
class ShortestPathFinder {
private Graph graph = new Graph();
private Vertex source = new Vertex(0, null);
private Vertex destination = new Vertex(0,null);
private Map<Vertex,Double> minimumWeightToVertices = new HashMap();
private Map<Vertex,Vertex> previousVertex = new HashMap();
private Set<Vertex> visited = new HashSet();
private Map<Vertex,Double> neighbors = new HashMap();
public Optional<Path> findShortestPath(Graph graph, Vertex source, Vertex destination) {
this.graph = graph;
this.source = graph.getVertex(source);
this.destination = graph.getVertex(destination);
Optional<Path> pathFound = Optional.empty();
//start queue at source vertex
source.setDistance(0);
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
priorityQueue.add(source);
source.setVisited(true);
while( !priorityQueue.isEmpty() ){
// Getting the minimum distance vertex from priority queue
Vertex actualVertex = priorityQueue.poll();
//get Neighbors of source vertex
neighbors = graph.getNeighbours(actualVertex);
//find Neighbor with lowest weight
for(Entry<Vertex, Double> neighbor : neighbors.entrySet()){
Vertex v = neighbor.getKey();
if(v.getID() == destination.getID()) {
minimumWeightToVertices.put(v,v.getDistance());
v.setPredecessor(actualVertex);
previousVertex.put(actualVertex,v);
priorityQueue.add(v);
// found, set pathFound = Optional.of(path)
Path path = new Path();
pathFound = Optional.of(path);
}
else if(visited.contains(v) == false)
{
double newDistance = actualVertex.getDistance() + neighbor.getValue();
//when found min add to minmumWeightToVertices
if( newDistance < v.getDistance() ){
priorityQueue.remove(v);
v.setDistance(newDistance);
minimumWeightToVertices.put(v,newDistance);
v.setPredecessor(actualVertex);
previousVertex.put(actualVertex,v);
priorityQueue.add(v);
System.out.println("Added: " + v.getID());
}
}
}
//When visited add to visited so not visited again
actualVertex.setVisited(true);
visited.add(actualVertex);
//continue getting neighbors with lowest index until destination reached
}
return pathFound;
}
public void getPath() {
//print all info using previous Vertex and print out edge info from it
for (Entry<Vertex, Vertex> entry : previousVertex.entrySet()) {
System.out.println("ID: " + entry.getKey().getID() + " Name: " + entry.getKey().getName() +
" to " + "ID: " + entry.getValue().getID() + " Name: " + entry.getValue().getName());
}
}
}
Край
public class Edge {
private double weight;
private Vertex startVertex;
private Vertex targetVertex;
private String extra;
public Edge(double weight, Vertex startVertex, Vertex targetVertex, String extra) {
this.weight = weight;
this.startVertex = startVertex;
this.targetVertex = targetVertex;
this.extra = extra;
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
public Vertex getStartVertex() {
return startVertex;
}
public void setStartVertex (Vertex startVertex) {
this.startVertex = startVertex;
}
public Vertex getTargetVertex() {
return targetVertex;
}
public void setTargetVertex(Vertex targetVertex) {
this.targetVertex = targetVertex;
}
public String getExtra() {
return extra;
}
public void setExtra(String extra) {
this.extra = extra;
}
}
Vertex
public class Vertex implements Comparable<Vertex> {
private int ID;
private String name;
private List<Edge> adjacenciesList;
private boolean visited;
private Vertex predecessor;
private double distance = Double.MAX_VALUE;
public Vertex(int ID, String name) { //(Int ID, String name)?
this.ID = ID;
this.name = name;
this.adjacenciesList = new ArrayList<>();
}
public void addNeighbour(Edge edge) {
this.adjacenciesList.add(edge);
}
public String getName() {
return name;
}
public void setID(int ID) {
this.ID = ID;
}
public int getID() {
return ID;
}
public void setName(String name) {
this.name = name;
}
public List<Edge> getAdjacenciesList() {
return adjacenciesList;
}
public void setAdjacenciesList(List<Edge> adjacenciesList) {
this.adjacenciesList = adjacenciesList;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Vertex getPredecessor() {
return predecessor;
}
public void setPredecessor(Vertex predecessor) {
this.predecessor = predecessor;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
@Override
public String toString() {
return this.name;
}
@Override
public int compareTo(Vertex otherVertex) {
return Double.compare(this.distance, otherVertex.getDistance());
}
}
ReadInput
public class ReadInput {
Vertex[] vertex = new Vertex[25252];
final String DELIMITER = ",";
int indexVertex = 0;
//public Vertex[] readVertices() throws NumberFormatException, IOException {
public Graph readFromStream() throws NumberFormatException, IOException {
Graph graph = new Graph();
//25252 number of elements in Place.txt file
//Delimiter used in CSV file
String line = "";
//Create the file reader
BufferedReader fileReader = new BufferedReader(new FileReader("Place.txt"));
String IDString = null;
String name = null;
int ID = 0;
//Read the file line by line
while ((line = fileReader.readLine()) != null)
{
//Get all tokens available in line
String[] tokens = line.split(DELIMITER);
//for(String token : tokens)
//{
IDString = tokens[0];
name = tokens[1];
ID = Integer.parseInt(IDString);
//}
vertex[indexVertex] = new Vertex(ID,name);
graph.addVertex(ID,name);
//System.out.println(indexVertex +":" + vertex[indexVertex].getID());
indexVertex++;
}
fileReader.close();
//return vertex;
//}
//public Edge[] readEdges() throws NumberFormatException, IOException {
Edge[] edge = new Edge[127807];
int indexEdge = 0;
String line2 = "";
BufferedReader fileReader2 = new BufferedReader(new FileReader("Road.txt"));
String valueString = null;
String vertex1IDName = null;
String vertex2IDName = null;
String extra = null;
float value = 0;
int vertex1ID = 0;
int vertex2ID = 0;
//Read the file line by line
while ((line2 = fileReader2.readLine()) != null)
{
//Get all tokens available in line
String[] tokens2 = line2.split(DELIMITER);
//for(String token1 : tokens2)
//{
vertex1IDName = tokens2[0];
vertex2IDName = tokens2[1];
valueString = tokens2[2];
if(tokens2.length - 1 == 3) {
extra = tokens2[tokens2.length - 1];
}
else {
extra = "";
}
vertex1ID = Integer.parseInt(vertex1IDName);
vertex2ID = Integer.parseInt(vertex2IDName);
value = Float.parseFloat(valueString);
//adds all edges with null vertex names, need to account for edges that connect to actual vertices?
Vertex vertex1 = new Vertex(vertex1ID,"null");
Vertex vertex2 = new Vertex(vertex2ID,"null");
graph.addEdge(value,vertex1, vertex2, extra);
}
fileReader2.close();
return graph;
//return edge;
}
public Vertex calcualteDestination() {
Scanner scanUserInput = new Scanner(System.in);
System.out.println("Enter the Destination Name:");
String destinationName = scanUserInput.nextLine();
scanUserInput.close();
Vertex Destination = new Vertex(0,null);
for(int i = 0; i<indexVertex; i++) {
if(destinationName.equals(vertex[i].getName())){
Destination.setID(vertex[i].getID());
Destination.setName(vertex[i].getName());
}
}
return Destination;
}
public Vertex calculatesSource() {
Scanner scanUserInput = new Scanner(System.in);
System.out.println("Enter the Source Name:");
String sourceName = scanUserInput.nextLine();
Vertex Source = new Vertex(0, null);
for(int i = 0; i<indexVertex; i++) {
if(sourceName.equals(vertex[i].getName())){
Source.setID(vertex[i].getID());
Source.setName(vertex[i].getName());
}
}
return Source;
}
}
Main
ppublic class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
ReadInput graphReader = new ReadInput();
Graph graph = graphReader.readFromStream();
Vertex source = graphReader.calculatesSource();
Vertex destination = graphReader.calcualteDestination();
//graph.printEdges();
//graph.printVertices();
ShortestPathFinder finder = new ShortestPathFinder();
Optional<Path> possiblePath = finder.findShortestPath(graph,source,destination);
if(possiblePath.isPresent() == false) {
System.out.println("No path found");
}
else {
System.out.println("Shortest path:");
finder.getPath();
}
}
}