Java最短路径算法详解（Dijkstra算法从零入门）

准备工作：理解图的表示

在Java中，我们通常用邻接矩阵或邻接表来表示图。本教程使用邻接表，因为它在稀疏图中更节省空间。

Java实现Dijkstra算法

下面是一个完整的、易于理解的Dijkstra算法Java实现：

import java.util.*;public class DijkstraShortestPath {    // 图的顶点数量    private static final int V = 6;    // 找到距离最小且未处理的顶点    private static int minDistance(int[] dist, boolean[] sptSet) {        int min = Integer.MAX_VALUE, minIndex = -1;        for (int v = 0; v < V; v++) {            if (!sptSet[v] && dist[v] <= min) {                min = dist[v];                minIndex = v;            }        }        return minIndex;    }    // 打印最短距离数组    private static void printSolution(int[] dist) {        System.out.println("顶点\t距离起点的最短距离");        for (int i = 0; i < V; i++) {            System.out.println(i + "\t" + dist[i]);        }    }    // Dijkstra算法主函数    public static void dijkstra(int[][] graph, int src) {        int[] dist = new int[V]; // 存储最短距离        boolean[] sptSet = new boolean[V]; // 记录是否已处理        // 初始化所有距离为无穷大，起点为0        Arrays.fill(dist, Integer.MAX_VALUE);        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];                }            }        }        printSolution(dist);    }    // 测试示例    public static void main(String[] args) {        // 邻接矩阵表示的图（0表示无边）        int[][] graph = {            {0, 4, 0, 0, 0, 0},            {4, 0, 8, 0, 0, 0},            {0, 8, 0, 7, 0, 4},            {0, 0, 7, 0, 9, 14},            {0, 0, 0, 9, 0, 10},            {0, 0, 4, 14, 10, 0}        };        dijkstra(graph, 0); // 从顶点0开始计算最短路径    }}

代码解析

• dist数组：存储从起点到每个顶点的最短距离。
• sptSet数组：记录哪些顶点已经被处理（即最短路径已确定）。
• minDistance方法：从未处理的顶点中找出距离最小的那个。
• 主循环：每次选出一个最近的未处理顶点，然后更新其邻居的距离。

运行结果说明

当你运行上述代码时，程序会输出从顶点0到图中所有其他顶点的最短距离。例如：

顶点	距离起点的最短距离0	01	42	123	194	215	16  

应用场景与扩展

Java路径查找技术广泛应用于：

• 地图导航（如高德、百度地图）
• 网络数据包路由
• 社交网络中“六度空间”关系查找
• 游戏中的NPC自动寻路

如果你需要处理负权边，可以考虑使用Bellman-Ford算法；如果要找所有顶点对之间的最短路径，Floyd-Warshall算法会更适合。

总结

通过本教程，你已经掌握了如何在Java中实现Dijkstra算法教程的核心逻辑。记住，理解图论Java实现的关键在于多练习、多画图。尝试修改上面的图结构，看看结果如何变化，这是巩固知识的最佳方式！

希望这篇关于Java最短路径算法的入门指南对你有所帮助。祝你编程愉快！