编写java代码,有向图,节点为node 分别为node 1 node2 边为edge,并求该图形的两点之间最短路径及长度。如果不可达则写成-1
时间: 2023-08-31 07:34:45 浏览: 112
### 回答1:
下面是一个简单的 Java 代码,它实现了有向图,其中节点表示为Node,边表示为Edge。我们可以使用Dijkstra算法来计算两个节点之间的最短路径。
```java
import java.util.*;
class Node {
public int val;
public List<Edge> edges;
public Node(int val) {
this.val = val;
this.edges = new ArrayList<>();
}
}
class Edge {
public int weight;
public Node dest;
public Edge(int weight, Node dest) {
this.weight = weight;
this.dest = dest;
}
}
public class Graph {
private Map<Integer, Node> nodes;
public Graph() {
this.nodes = new HashMap<>();
}
public void addNode(int val) {
nodes.put(val, new Node(val));
}
public void addEdge(int src, int dest, int weight) {
Node srcNode = nodes.get(src);
Node destNode = nodes.get(dest);
srcNode.edges.add(new Edge(weight, destNode));
}
public int shortestPath(int startVal, int endVal) {
Node start = nodes.get(startVal);
Node end = nodes.get(endVal);
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
Map<Node, Integer> dist = new HashMap<>();
pq.add(start);
dist.put(start, 0);
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (cur == end) {
return dist.get(end);
}
for (Edge edge : cur.edges) {
Node neighbor = edge.dest;
int newDist = dist.get(cur) + edge.weight;
if (!dist.containsKey(neighbor) || newDist < dist.get(neighbor)) {
dist.put(neighbor, newDist);
pq.add(neighbor);
}
}
}
return -1;
}
public static void main(String[] args) {
Graph g = new Graph();
g.addNode(1);
g.addNode(2);
g.addEdge(1, 2, 10);
int shortestPath = g.shortestPath(1, 2);
System.out.println(shortestPath); // Output: 10
}
}
```
在上面的代码中,我们首先定义了两个类,Node和Edge,分别表示图中的节点和边。然后我们定义了一个Graph类,它包含一个nodes map,用于存储所有节点。在Graph类中,我们定义了addNode方法用于添加新节点,addEdge方法用于添加新边,并使用Dijkstra算法实现了shortestPath方法来计算两个节点之间的最短路径。在main方法中,我们首先创建了一个图,并向其中添加了一个节点和一条边,然后调用shortestPath方法来计算从节点1到节点2的最短路径长度。
### 回答2:
以下是一种用Java编写的求有向图中两点之间最短路径及长度的方法:
首先,我们需要定义一个Node类表示节点,其中包括节点的名称和与该节点相邻的边的列表:
```java
class Node {
String name;
List<Edge> edges;
Node(String name) {
this.name = name;
this.edges = new ArrayList<>();
}
}
class Edge {
Node node;
int weight;
Edge(Node node, int weight) {
this.node = node;
this.weight = weight;
}
}
```
然后,我们可以创建一个有向图类,其中包括节点的集合和一些方法来添加节点和边以及计算最短路径长度:
```java
class DirectedGraph {
List<Node> nodes;
DirectedGraph() {
this.nodes = new ArrayList<>();
}
void addNode(Node node) {
nodes.add(node);
}
void addEdge(Node source, Node destination, int weight) {
Edge edge = new Edge(destination, weight);
source.edges.add(edge);
}
int shortestPathLength(Node start, Node end) {
Map<Node, Integer> distances = new HashMap<>();
for (Node node : nodes) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(start, 0);
Queue<Node> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Edge edge : current.edges) {
Node neighbor = edge.node;
int newDistance = distances.get(current) + edge.weight;
if (newDistance < distances.get(neighbor)) {
distances.put(neighbor, newDistance);
queue.add(neighbor);
}
}
}
if (distances.get(end) == Integer.MAX_VALUE) {
return -1; // 不可达
} else {
return distances.get(end);
}
}
}
```
最后,我们可以使用这个有向图类来求解两点之间最短路径及长度。以下是一个示例:
```java
public class Main {
public static void main(String[] args) {
DirectedGraph graph = new DirectedGraph();
Node node1 = new Node("node1");
Node node2 = new Node("node2");
graph.addNode(node1);
graph.addNode(node2);
graph.addEdge(node1, node2, 10);
graph.addEdge(node2, node1, 5);
int shortestPathLength = graph.shortestPathLength(node1, node2);
System.out.println("最短路径长度:" + shortestPathLength);
}
}
```
在这个例子中,我们创建了一个有向图,包含两个节点node1和node2,其中node1到node2的边权重为10,node2到node1的边权重为5。然后我们使用`graph.shortestPathLength(node1, node2)`方法来计算最短路径长度,并将结果打印出来。
### 回答3:
要编写Java代码求两点之间最短路径及长度,可以使用Dijkstra算法。首先,需要定义两个类,一个表示节点,一个表示边。
节点类的定义如下:
```java
public class Node {
private String name;
private List<Edge> edges;
public Node(String name) {
this.name = name;
this.edges = new ArrayList<>();
}
public String getName() {
return name;
}
public List<Edge> getEdges() {
return edges;
}
public void addEdge(Edge edge) {
edges.add(edge);
}
}
```
边类的定义如下:
```java
public class Edge {
private Node startNode;
private Node endNode;
private int weight;
public Edge(Node startNode, Node endNode, int weight) {
this.startNode = startNode;
this.endNode = endNode;
this.weight = weight;
}
public Node getStartNode() {
return startNode;
}
public Node getEndNode() {
return endNode;
}
public int getWeight() {
return weight;
}
}
```
然后,我们可以利用Dijkstra算法求解最短路径及长度:
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
// 创建节点
Node node1 = new Node("node1");
Node node2 = new Node("node2");
// 创建边
Edge edge1 = new Edge(node1, node2, 10);
Edge edge2 = new Edge(node2, node1, 5);
// 添加边到节点
node1.addEdge(edge1);
node2.addEdge(edge2);
// 调用最短路径方法
int shortestPathLength = getShortestPathLength(node1, node2);
System.out.println("最短路径长度:" + shortestPathLength);
}
public static int getShortestPathLength(Node startNode, Node endNode) {
Set<Node> visited = new HashSet<>();
Map<Node, Integer> distance = new HashMap<>();
PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(distance::get));
distance.put(startNode, 0);
queue.add(startNode);
while (!queue.isEmpty()) {
Node currentNode = queue.poll();
visited.add(currentNode);
if (currentNode == endNode) {
return distance.get(currentNode);
}
for (Edge edge : currentNode.getEdges()) {
Node neighborNode = edge.getEndNode();
int newDistance = distance.get(currentNode) + edge.getWeight();
if (!visited.contains(neighborNode)) {
if (!distance.containsKey(neighborNode) || newDistance < distance.get(neighborNode)) {
distance.put(neighborNode, newDistance);
queue.add(neighborNode);
}
}
}
}
return -1; // 不可达的情况
}
}
```
在此示例中,我们创建了两个节点node1和node2,并设置了它们之间的边edge1和edge2。然后,我们调用getShortestPathLength方法来获取最短路径的长度,并打印出来。
请注意,此示例中的节点和边仅用于演示,你可以根据实际需求进行修改和扩展。
阅读全文