代码模块化、去耦合,构建和测试过程合理 编写java代码有向图, 节点 为node, 边为edge, 求该图形的两点之间最短路径及长度。如果不可达则写成-1
时间: 2023-03-19 19:22:31 浏览: 59
为了求解一个有向图的最短路径和长度,可以使用 Dijkstra 算法或者 Bellman-Ford 算法。这里我使用 Dijkstra 算法实现该功能。
下面是 Java 代码实现,其中包含了对图的节点和边的定义,以及最短路径算法的实现。代码使用了模块化和去耦合的设计思想,通过面向对象的方式来组织代码。同时,我也考虑了构建和测试过程的合理性,使用了 JUnit 来编写单元测试。
```java
import java.util.*;
class Node {
public final String name;
public List<Edge> neighbors;
public boolean visited;
public double distance = Double.MAX_VALUE;
public Node previous;
public Node(String name) {
this.name = name;
this.neighbors = new ArrayList<Edge>();
}
public void addNeighbor(Edge edge) {
this.neighbors.add(edge);
}
@Override
public String toString() {
return this.name;
}
}
class Edge {
public final Node start;
public final Node end;
public final double weight;
public Edge(Node start, Node end, double weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
public class ShortestPath {
public static List<Node> getShortestPath(Node start, Node end) {
start.distance = 0;
PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>(Comparator.comparingDouble(node -> node.distance));
priorityQueue.add(start);
while (!priorityQueue.isEmpty()) {
Node current = priorityQueue.poll();
if (current == end) {
break;
}
for (Edge edge : current.neighbors) {
Node neighbor = edge.end;
double distance = current.distance + edge.weight;
if (distance < neighbor.distance) {
priorityQueue.remove(neighbor);
neighbor.distance = distance;
neighbor.previous = current;
priorityQueue.add(neighbor);
}
}
}
List<Node> shortestPath = new ArrayList<Node>();
for (Node node = end; node != null; node = node.previous) {
shortestPath.add(node);
}
Collections.reverse(shortestPath);
return shortestPath;
}
public static double getShortestPathLength(Node start, Node end) {
List<Node> shortestPath = getShortestPath(start, end);
if (shortestPath.size() == 0 || shortestPath.get(shortestPath.size() - 1) != end) {
return -1;
}
return end.distance;
}
public static void main(String[] args) {
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
nodeA.addNeighbor(new Edge(nodeA, nodeB, 10));
nodeA.addNeighbor(new Edge(nodeA, nodeC, 20));
nodeB.addNeighbor(new Edge(nodeB, nodeD, 15));
nodeC.addNeighbor(new Edge(nodeC, nodeD, 30));
nodeC.addNeighbor(new Edge(nodeC, nodeE, 5));
nodeD.addNeighbor(new Edge(nodeD, nodeE, 10));
Node start = nodeA;
Node end = nodeE;
double shortestPathLength = getShortestPathLength(start, end);