图论算法：Dijkstra算法详解与Java实现，透彻理解算法原理，轻松实现最短路径计算

# 1. 图论算法概览

图论算法是计算机科学中用于解决图论问题的算法。图论是一种数学模型，用于表示由节点（顶点）和边组成的结构。图论算法广泛应用于网络路由、社交网络分析、交通规划等领域。

图论算法主要分为两大类：最短路径算法和最小生成树算法。最短路径算法用于寻找图中两点之间的最短路径，而最小生成树算法用于寻找图中连接所有节点的最小权重子图。

本章将介绍图论算法的基本概念、分类和应用，为后续章节的深入讨论奠定基础。

# 2. Dijkstra算法理论基础

### 2.1 图论基础知识

#### 2.1.1 图的概念和基本术语

**图**：图是一种数据结构，用于表示对象之间的关系。它由一组称为**顶点**（或节点）的对象和一组称为**边**（或弧）的关系组成。

**顶点**：图中的对象，通常用数字或字母表示。

**边**：连接两个顶点的关系，通常用线段表示。

**权重**：边上附加的值，表示边上的距离、成本或其他度量。

#### 2.1.2 图的表示方式

**邻接矩阵**：一个二维数组，其中元素表示顶点之间的权重。

**邻接表**：一个数组，其中每个元素是一个链表，包含与该顶点相邻的顶点和权重。

### 2.2 Dijkstra算法原理

#### 2.2.1 算法思想和步骤

Dijkstra算法是一种贪心算法，用于寻找图中从一个源顶点到其他所有顶点的最短路径。其基本思想是：

1. 初始化源顶点到其他所有顶点的距离为无穷大，源顶点到自身的距离为0。
2. 重复以下步骤，直到所有顶点都被访问过：
- 选择当前距离最小的未访问顶点。
- 将该顶点标记为已访问。
- 更新该顶点相邻顶点的距离，如果通过该顶点到相邻顶点的路径更短。

#### 2.2.2 算法复杂度分析

Dijkstra算法的时间复杂度为 `O(V^2)`，其中V是图中的顶点数。这是因为算法在每次迭代中访问一个顶点，并在最坏情况下访问所有V个顶点。

import java.util.*;

public class Dijkstra {

    private int[] distance; // 从源顶点到每个顶点的距离
    private boolean[] visited; // 顶点是否已访问
    private Map<Integer, List<Edge>> graph; // 图的邻接表表示

    public Dijkstra(Map<Integer, List<Edge>> graph) {
        this.graph = graph;
        int V = graph.size();
        distance = new int[V];
        visited = new boolean[V];
    }

    public void computeShortestPaths(int source) {
        // 初始化距离
        for (int i = 0; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        distance[source] = 0;

        // 贪心算法
        while (true) {
            // 找到当前距离最小的未访问顶点
            int minDistance = Integer.MAX_VALUE;
            int minVertex = -1;
            for (int i = 0; i < distance.length; i++) {
                if (!visited[i] && distance[i] < minDistance) {
                    minDistance = distance[i];
                    minVertex = i;
                }
            }

            // 如果所有顶点都已访问，则算法结束
            if (minVertex == -1) {
                break;
            }

            // 将该顶点标记为已访问
            visited[minVertex] = true;

            // 更新相邻顶点的距离
            for (Edge edge : graph.get(minVertex)) {
                int neighbor = edge.getDestination();
                int newDistance = distance[minVertex] + edge.getWeight();
                if (newDistance < distance[neighbor]) {
                    distance[neighbor] = newDistance;
                }
            }
        }
    }

    public int getDistance(int vertex) {
        return distance[vertex];
    }

    public static void main(String[] args) {
        // 创建一个图
        Map<Integer, List<Edge>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(new Edge(1, 4), new Edge(2, 2)));
        graph.put(1, Arrays.asList(new Edge(2, 3)));
        graph.put(2, Arrays.asList(new Edge(3, 2), new Edge(4, 5)));
        graph.put(3, Arrays.asList(new Edge(4, 1)));
        graph.put(4, Collections.emptyList());

        // 计算从顶点0到其他所有顶点的最短路径
        Dijkstra dijkstra = new Dijkstra(graph);
        dijkstra.computeShortestPaths(0);

        // 打印最短路径
        for (int i = 0; i < dijkstra.distance.length; i++) {
            System.out.println("最短路径从0到" + i + ": " + dijkstra.getDistance(i));
        }
    }
}

class Edge {

    private int destination;
    private int weight;

    public Edge(int destination, int weight) {
        this.destination = destination;
        this.weight = weight;
    }

    public int getDestination() {
        return destination;
    }

    public int getWeight() {
        return weight;
    }
}

**代码逻辑逐行解读：**

* `computeShortestPaths` 方法：计算从源顶点到其他所有顶点的最短路径。
* 初始化距离数组 `distance`，将所有顶点到源顶点的距离设为无穷大，源顶点到自身的距离设为0。
* 进入贪心算法循环：
* 找到当前距离最小的未访问顶点。
* 将该顶点标记为已访问。
* 更新该顶点相邻顶点的距离。
* 如果所有顶点都已访问，则算法结束。
*