编写java代码,节点为 node 分别为node1 node2 边为edge, 并求该图形的两点之间最短路径及长度。如果不可达则写成-1
时间: 2023-03-19 11:22:23 浏览: 126
java实现dijkstra最短路径寻路算法
5星 · 资源好评率100%
以下是使用Java编写的示例代码,使用邻接矩阵表示图形。首先,定义一个`Graph`类来表示图形,其中包括一个二维邻接矩阵和节点数:
```java
public class Graph {
private int[][] matrix;
private int numNodes;
public Graph(int numNodes) {
this.numNodes = numNodes;
matrix = new int[numNodes][numNodes];
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
matrix[i][j] = -1;
}
}
}
public void addEdge(int from, int to, int weight) {
matrix[from][to] = weight;
}
public int shortestPath(int start, int end) {
int[] dist = new int[numNodes];
boolean[] visited = new boolean[numNodes];
for (int i = 0; i < numNodes; i++) {
dist[i] = Integer.MAX_VALUE;
visited[i] = false;
}
dist[start] = 0;
for (int i = 0; i < numNodes - 1; i++) {
int u = findMin(dist, visited);
visited[u] = true;
for (int v = 0; v < numNodes; v++) {
if (!visited[v] && matrix[u][v] != -1 && dist[u] != Integer.MAX_VALUE
&& dist[u] + matrix[u][v] < dist[v]) {
dist[v] = dist[u] + matrix[u][v];
}
}
}
return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];
}
private int findMin(int[] dist, boolean[] visited) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < numNodes; i++) {
if (!visited[i] && dist[i] < min) {
min = dist[i];
minIndex = i;
}
}
return minIndex;
}
}
```
其中,`addEdge`方法用于添加边,`shortestPath`方法用于计算两点之间的最短路径长度,`findMin`方法用于在未访问的节点中查找距离起点最近的节点。
下面是使用示例:
```java
public class Main {
public static void main(String[] args) {
Graph graph = new Graph(2);
graph.addEdge(0, 1, 2);
int shortestPath = graph.shortestPath(0, 1);
System.out.println(shortestPath);
}
}
```
这个示例创建了一个只有两个节点的图形,并将它们连接成一条边。然后,它计算了节点0和节点1之间的最短路径长度,并将其打印到控制台上。在这个例子中,输出结果是2,因为这两个节点之间只有一条边,权重为2。
注意,如果两个节点之间没有路径,`shortestPath`方法将返回-1。
阅读全文