如何使用Java函数实现最短路径算法的Dijkstra算法

Dijkstra算法是一种经典的用于解决图中单源最短路径问题的算法。它采用贪心策略，通过不断选择当前最短路径的节点来逐步确定最短路径。下面我们将介绍如何使用Java函数实现Dijkstra算法。

首先，我们需要定义一个Graph类来表示图。这个类可以包含一个节点的集合以及节点之间的边。我们可以使用邻接矩阵或邻接表来存储边的信息，这里我们选择使用邻接表。

class Graph {
    private int numVertices;
    private LinkedList<Edge> adjLists[];

    // 构造函数
    Graph(int numVertices) {
        this.numVertices = numVertices;
        adjLists = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjLists[i] = new LinkedList<>();
        }
    }

    // 添加边
    void addEdge(int src, int dest, int weight) {
        Edge edge = new Edge(src, dest, weight);
        adjLists[src].add(edge);
    }
}

接下来，我们定义一个Edge类来表示图中的边。

class Edge {
    int src, dest, weight;

    // 构造函数
    Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

然后，我们需要定义一个函数来实现Dijkstra算法。这个函数接受一个Graph对象和一个起始节点作为输入，并返回一个最短路径的数组。

class Dijkstra {
    static final int INF = 99999;

    // Dijkstra算法
    static void dijkstra(Graph graph, int src) {
        int numVertices = graph.numVertices;
        int dist[] = new int[numVertices];
        boolean visited[] = new boolean[numVertices];

        for (int i = 0; i < numVertices; i++) {
            dist[i] = INF;
            visited[i] = false;
        }

        dist[src] = 0;

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

            for (Edge edge : graph.adjLists[u]) {
                int v = edge.dest;
                int weight = edge.weight;

                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        printSolution(dist);
    }

    // 找到距离最小的节点
    static int minDistance(int dist[], boolean visited[]) {
        int min = INF;
        int minIndex = -1;

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

        return minIndex;
    }

    // 打印最短路径
    static void printSolution(int dist[]) {
        System.out.println("节点  距离");

        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + "       " + dist[i]);
        }
    }
}

最后，我们可以在主函数中创建一个Graph对象，添加边，并调用dijkstra函数来计算最短路径。

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 4, 5);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 4, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(3, 2, 8);
        graph.addEdge(3, 0, 7);
        graph.addEdge(4, 1, 3);
        graph.addEdge(4, 2, 9);
        graph.addEdge(4, 3, 2);

        Dijkstra.dijkstra(graph, 0);
    }
}

以上就是使用Java函数实现Dijkstra算法的步骤。通过定义Graph类表示图，Edge类表示边，以及使用Dijkstra类来实现Dijkstra算法，我们可以方便地找到图中单源最短路径并打印出来。