java使用Dijkstra算法实现单源最短路径

Java使用Dijkstra算法实现单源最短路径攻略

算法简介

Dijkstra算法是一种经典的计算图的单源最短路径的算法。它的基本思想是从起始点开始，首先确定该点到其他所有点的最短距离，然后以最短距离作为中介点，依次直到所有点的最短路径都被确定。Dijkstra算法主要应用在网络路由、航空等行业中。

算法步骤

• 将图中节点分为两个集合：已确定路径的节点集合和未确定路径的节点集合，分别使用两个数组visited和distance记录。
• 初始化过程：设置起始节点为已确定路径的节点，将其distance值设置为0，将所有其他节点的distance值设置为正无穷。
• 重复以下过程，直到所有节点都被添加到已确定的路径集合中：
  • 从未确定路径的节点集合中选出当前distance值最小的节点，将其加入到已确定的路径集合中。
  • 更新该节点的相邻节点的distance值，如果distance变短了，则更新其父节点和最短路径。

Java代码实现

以下代码实现了Dijkstra算法，用于求解最短路径。图使用邻接矩阵来表示，Graph类包含两个方法：dijsktra方法用于求解最短路径，printResult方法用于输出结果。

public class Graph {
    private int vertexCount;
    private int[][] adjacencyMatrix;

    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacencyMatrix = new int[vertexCount][vertexCount];
    }

    public void dijkstra(int sourceVertex) {
        boolean[] visited = new boolean[vertexCount];
        int[] distance = new int[vertexCount];

        for (int i = 0; i < vertexCount; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        distance[sourceVertex] = 0;

        for (int i = 0; i < vertexCount - 1; i++) {
            int minDistance = Integer.MAX_VALUE;
            int minDistanceVertex = -1;

            for (int j = 0; j < vertexCount; j++) {
                if (!visited[j] && distance[j] < minDistance) {
                    minDistance = distance[j];
                    minDistanceVertex = j;
                }
            }

            visited[minDistanceVertex] = true;
            for (int k = 0; k < vertexCount; k++) {
                int edgeDistance = adjacencyMatrix[minDistanceVertex][k];
                if (edgeDistance > 0 && ((minDistance + edgeDistance) < distance[k])) {
                    distance[k] = minDistance + edgeDistance;
                }
            }
        }

        printResult(distance, sourceVertex);
    }

    public void printResult(int[] distance, int sourceVertex) {
        System.out.println("最短路径从起点 " + sourceVertex + " 到各点的距离：");
        for (int i = 0; i < vertexCount; i++) {
            System.out.println("点 " + i + ": 距离 = " + distance[i]);
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(9);
        graph.adjacencyMatrix = new int[][]{ {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}};
        graph.dijkstra(0);
    }
}

示例说明

以下是一个基于上述代码实现的示例：

假设有以下图中的图，其中矩阵元素代表两点间的距离，0表示自身或不连通。

{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}

我们将起点设置为节点0，执行dijkstra方法，可以得到最短路径为：

最短路径从起点 0 到各点的距离：
点 0: 距离 = 0
点 1: 距离 = 4
点 2: 距离 = 12
点 3: 距离 = 19
点 4: 距离 = 21
点 5: 距离 = 11
点 6: 距离 = 9
点 7: 距离 = 8
点 8: 距离 = 14

这意味着从节点0到节点8的最短路径为14，该路径穿过节点7。

另一个示例，我们将起点设置为节点8，执行dijkstra方法：

最短路径从起点 8 到各点的距离：
点 0: 距离 = 14
点 1: 距离 = 19
点 2: 距离 = 2
点 3: 距离 = 6
点 4: 距离 = 14
点 5: 距离 = 12
点 6: 距离 = 6
点 7: 距离 = 7
点 8: 距离 = 0

这意味着从节点8到节点2的最短路径为2，该路径穿过节点5。