java计算最短路径的代码

Java中可以通过使用Dijkstra算法来计算最短路径。算法的代码实现大致如下： // 初始化
int[] dist = new int[V];
boolean[] sptSet = new boolean[V]; // 将所有距离初始化为无穷大，并将sptSet[]都设置为false
for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
} // 将起点距离设置为0
dist[src] = 0; // 找出最短路径
for (int count = 0; count < V-1; count++)
{
// 从未放入集合的顶点中找出距离最小的顶点
int u = minDistance(dist, sptSet); // 将顶点放入集合
sptSet[u] = true; // 更新最小距离
for (int v = 0; v < V; v++) // 遍历所有顶点，更新最小距离
if (!sptSet[v] && graph[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
} // 返回最短路径
return dist[dest];

相关问题

Java实现最短路径算法

在 Java 中实现最短路径算法，你可以使用经典的Dijkstra算法或者A*算法。这里我给你一个使用Dijkstra算法的示例代码：

import java.util.*;

public class DijkstraAlgorithm {
    private int V;
    private int[][] graph;

    public DijkstraAlgorithm(int[][] graph) {
        this.V = graph.length;
        this.graph = graph;
    }

    public int[] findShortestPath(int source) {
        int[] dist = new int[V]; // 存储源节点到各个节点的最短距离
        boolean[] visited = new boolean[V]; // 标记节点是否已被访问

        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化距离为无穷大
        dist[source] = 0; // 源节点到自身的距离为0

        for (int count = 0; count < V - 1; count++) {
            int u = findMinimumDistance(dist, visited);
            visited[u] = true;

            for (int v = 0; v < V; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        return dist;
    }

    private int findMinimumDistance(int[] dist, boolean[] visited) {
        int minDist = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] <= minDist) {
                minDist = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };

        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
        int[] shortestDistances = dijkstra.findShortestPath(0);

        System.out.println("最短路径：");
        for (int i = 1; i < shortestDistances.length; i++) {
            System.out.println("从节点 " + source + " 到节点 " + i + " 的最短距离为：" + shortestDistances[i]);
        }
    }
}

这个示例代码使用邻接矩阵来表示图，其中图的顶点数由变量 V 来表示，图的边权重由二维数组 graph 来表示。你可以根据自己的需求修改图的结构。

在示例代码中，`findShortestPath` 方法使用了 Dijkstra 算法来计算从源节点到其他所有节点的最短路径。`main` 方法展示了如何使用这个算法来计算最短路径并输出结果。

希望这个示例代码能帮助到你！如果你对其他算法或者实现有疑问，请随时提问。

java实现最短路径算法

Java实现最短路径算法通常使用Dijkstra算法或者Bellman-Ford算法。

以下是使用Dijkstra算法实现最短路径的Java代码示例：

import java.util.*;

public class DijkstraAlgorithm {

    private static final int NO_PARENT = -1;

    private static void dijkstra(int[][] adjacencyMatrix, int startVertex) {
        int nVertices = adjacencyMatrix[0].length;
        int[] shortestDistances = new int[nVertices];
        boolean[] visited = new boolean[nVertices];
        shortestDistances[startVertex] = 0;
        int[] parents = new int[nVertices];
        parents[startVertex] = NO_PARENT;
        for (int i = 1; i < nVertices; i++) {
            int nearestVertex = -1;
            int shortestDistance = Integer.MAX_VALUE;
            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                if (!visited[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance) {
                    nearestVertex = vertexIndex;
                    shortestDistance = shortestDistances[vertexIndex];
                }
            }
            visited[nearestVertex] = true;
            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                int edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];
                if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex])) {
                    parents[vertexIndex] = nearestVertex;
                    shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
                }
            }
        }
        printSolution(startVertex, shortestDistances, parents);
    }

    private static void printSolution(int startVertex, int[] distances, int[] parents) {
        int nVertices = distances.length;
        System.out.print("Vertex\t Distance\tPath");
        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            if (vertexIndex != startVertex) {
                System.out.print("\n" + startVertex + " -> ");
                System.out.print(vertexIndex + " \t\t ");
                System.out.print(distances[vertexIndex] + "\t\t");
                printPath(vertexIndex, parents);
            }
        }
    }

    private static void printPath(int currentVertex, int[] parents) {
        if (currentVertex == NO_PARENT) {
            return;
        }
        printPath(parents[currentVertex], parents);
        System.out.print(currentVertex + " ");
    }

    public static void main(String[] args) {
        int[][] adjacencyMatrix = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            {0, 8, 0, 7, 0, 4, 0, 0, 2},
            {0, 0, 7, 0, 9, 14, 0, 0, 0},
            {0, 0, 0, 9, 0, 10, 0, 0, 0},
            {0, 0, 4, 14, 10, 0, 2, 0, 0},
            {0, 0, 0, 0, 0, 2, 0, 1, 6},
            {8, 11, 0, 0, 0, 0, 1, 0, 7},
            {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        dijkstra(adjacencyMatrix, 0);
    }
}

在上面的示例中，我们使用了邻接矩阵来表示图，并使用了Dijkstra算法来计算最短路径。使用邻接表也可以实现相同的算法。