uml diagram
Graph.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* @author:
* @description：TODO
* @date: 2023/3/4 1:53
*/
public class Graph {<!-- -->
public int v; // number of vertices
public int e; // number of edges
static public List<List<Path>> pathArrayList = new ArrayList<>();
static public List<Node> nodes = new ArrayList<>();
static public int [][]matrix;
Graph(List<Node> nodeList, List<Path> pathList){<!-- -->
for (Node node : nodeList) {<!-- -->
nodes.add(node);
pathArrayList.add(new ArrayList<Path>());
}
for(Path p: pathList){<!-- -->
pathArrayList.get(p.node1.index).add(p);
}
}
Graph(Node[] vertices, Node[][] edges){<!-- -->
for (Node node : vertices) {<!-- -->
nodes.add(node);
pathArrayList.add(new ArrayList<Path>());
}
for (int i = 0; i < edges.length; i + + ) {<!-- -->
Node node1 = edges[i][0];
Node node2 = edges[i][1];
pathArrayList.get(node1.index).add(new Path(node1, node2));
pathArrayList.get(node2.index).add(new Path(node2, node1));
}
matrix = new int[nodes.size()][nodes.size()];
for (int i = 0; i < nodes.size(); i + + ) {<!-- -->
for(Path p:pathArrayList.get(i)){<!-- -->
matrix[i][p.node2.index] = p.distance;
}
for (int j = 0; j < nodes.size(); j + + ) {<!-- -->
if(matrix[i][j] == 0){<!-- -->
matrix[i][j] = Integer.MAX_VALUE / 2;
}
}
matrix[i][i] = 0;
}
}
public List getVertices() {<!-- -->
return nodes;
}
public int getSize() {<!-- -->
return nodes.size();
}
public static int getTime(Node a, Node b){<!-- -->
for(Path p:pathArrayList.get(a.index)){<!-- -->
if(p.node2.index == b.index){<!-- -->
return p.distance;
}
}
return 0;
}
public static int addTime(Node a, Node b, Integer timeIn, String carName){<!-- -->
for(Path p:pathArrayList.get(a.index)){<!-- -->
if(p.node2.index == b.index){<!-- -->
p.timeWindow.timeIn.add(timeIn);
p.timeWindow.timeOut.add(timeIn + getTime(a, b));
p.timeWindow.carName.add(carName);
}
}
return 0;
}
public static boolean empty(Node a, Node b){<!-- -->
for(Path p:pathArrayList.get(a.index)){<!-- -->
if(p.node2.index == b.index){<!-- -->
return p.timeWindow.empty;
}
}
return false;
}
public static void changeEmpty(Node a, Node b){<!-- -->
for(Path p:pathArrayList.get(a.index)){<!-- -->
if(p.node2.index == b.index){<!-- -->
if(p.timeWindow.empty){<!-- -->
p.timeWindow.empty = false;}else{<!-- -->
p.timeWindow.empty = true;
}
}
}
}
public List<Node> getNeighbors(int i) {<!-- -->
List<Node> result = new ArrayList<>();
for(Path p: pathArrayList.get(i)){<!-- -->
result.add(p.node2);
}
return result;
}
public void printEdges(){<!-- -->
for (int i = 0; i < pathArrayList.size(); i + + ) {<!-- -->
System.out.println(nodes.get(i).getString() + ": ");
for (Path p: pathArrayList.get(i)) {<!-- -->
System.out.println(p.node1.getString() + "---" + p.node2.getString());
}
System.out.println();
}
}
public static Node getNode(int x, int y){<!-- -->
for (int i = 0; i < nodes.size(); i + + ) {<!-- -->
Node node = nodes.get(i);
if(node.x == x & amp; & amp; node.y == y){<!-- -->
return node;
}
}
return null;
}
public List<Node> dijkstra(Node v0, Node vi) {<!-- -->
List<Node> paths = new ArrayList<>();
// Starting from vertex vO, find the shortest path to vi
int n = nodes.size();
// listU records nodes that have not been processed yet
ArrayList<Integer> listU = new ArrayList<>();
// dist[] records the shortest weight from each node to the starting node
int[] dist = new int[n];
//Record the upper-level node of each node (used to contact the path from the node to the starting node)
int[] path = new int[n];
int start = v0.index; // Source point serial number
int end = vi.index; //End vertex number
//Initialize the U collection
for (int i = 0; i < n; i + + ) {<!-- -->
if (i == start) {<!-- --> // S={start}
continue;
}
listU.add(i); // u={vi}/{start}
}
//Initialize dist[],path[]
for (int i = 0; i < n; i + + ) {<!-- -->
// The current node weight of dist[] is equal to the weight of start->i node; initialize the shortest distance from all nodes to the source point
dist[i] = this.matrix[start][i];
if (this.matrix[start][i] == Integer.MAX_VALUE) {<!-- -->
path[i] = -1; // Node i is unreachable
} else {<!-- -->
path[i] = start; // If start can reach a certain point directly, it means that node i can directly access start;
}
}
//Record the node number of the minimum value
int minIndex;
do {<!-- -->
// dist array subscript
minIndex = listU.get(0);
for (int i = 1; i < listU.size(); i + + ) {<!-- -->
if (dist[listU.get(i)] < dist[minIndex]) {<!-- -->
minIndex = listU.get(i);
}
}
listU.remove((Integer) minIndex);
// Update the dist and path arrays, mainly to examine the inclusion of the minIndex node into S, that is, the change in the shortest path of the newly added node.
for (int i = 0; i < n; i + + ) {<!-- -->
if (this.matrix[minIndex][i] != 0 & amp; & amp; this.matrix[minIndex][i] < Integer.MAX_VALUE) {<!-- -->
// Find all adjacent points of minIndex
if (this.matrix[minIndex][i] + dist[minIndex] < dist[i]) {<!-- -->
// Newly added nodes are shorter
dist[i] = this.matrix[minIndex][i] + dist[minIndex];
path[i] = minIndex;
}
}
}
} while (minIndex != end & amp; & amp; !listU.isEmpty());
System.out.println("Starting point" + v0.getString() + "To target point" + vi.getString() + "Time consuming: " + dist[end] + ", global shortest path is: " );
String str = "" + vi.getString();
paths.add(vi);
int i = end;
do {<!-- -->
i = path[i];
paths.add(nodes.get(i));
str = nodes.get(i).getString() + "=>" + str;
} while (i != start);
System.out.println(str);
Collections.reverse(paths);
return paths;
}
}