使用java编写一个迪杰斯特拉算法

以下是使用Java编写的Dijkstra算法的示例代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class DijkstraAlgorithm {
    
    private int dist[];
    private boolean visited[];
    private PriorityQueue<Node> queue;
    private int numVertices;
    private ArrayList<ArrayList<Node>> adjacencylist;

    public DijkstraAlgorithm(int numVertices) {
        this.numVertices = numVertices;
        this.dist = new int[numVertices];
        this.visited = new boolean[numVertices];
        this.queue = new PriorityQueue<Node>(numVertices, new Node());
        this.adjacencylist = new ArrayList<ArrayList<Node>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            ArrayList<Node> innerList = new ArrayList<Node>();
            adjacencylist.add(innerList);
        }
    }

    public void addEdge(int source, int destination, int weight) {
        Node node = new Node(destination, weight);
        adjacencylist.get(source).add(node);
        node = new Node(source, weight);
        adjacencylist.get(destination).add(node);
    }

    public void dijkstra(int sourceVertex) {
        for (int i = 0; i < numVertices; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        queue.add(new Node(sourceVertex, 0));
        dist[sourceVertex] = 0;

        while (!queue.isEmpty()) {
            int v = queue.poll().node;
            visited[v] = true;

            for (int i = 0; i < adjacencylist.get(v).size(); i++) {
                Node neighbour = adjacencylist.get(v).get(i);
                if (!visited[neighbour.node]) {
                    int newDist = dist[v] + neighbour.cost;
                    if (newDist < dist[neighbour.node]) {
                        dist[neighbour.node] = newDist;
                    }
                    queue.add(new Node(neighbour.node, dist[neighbour.node]));
                }
            }
        }
        System.out.println(Arrays.toString(dist));
    }

    public static void main(String args[]) {
        int numVertices = 5;
        DijkstraAlgorithm d = new DijkstraAlgorithm(numVertices);

        d.addEdge(0, 1, 4);
        d.addEdge(0, 2, 1);
        d.addEdge(2, 1, 2);
        d.addEdge(1, 3, 1);
        d.addEdge(2, 3, 5);
        d.addEdge(3, 4, 3);

        d.dijkstra(0);
    }

    class Node implements Comparator<Node> {
        public int node;
        public int cost;

        public Node() {
        }

        public Node(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        @Override
        public int compare(Node node1, Node node2) {
            return Integer.compare(node1.cost, node2.cost);
        }
    }
}

在这个示例中，我们首先定义了一个名为DijkstraAlgorithm的类，其中包含一个构造函数，用于初始化必要的数据结构，以及addEdge函数，它用于添加图的边。我们还定义了一个内部类节点，用于表示图的节点和与其关联的代价。

在dijkstra函数中，我们首先将源节点的距离初始化为0，并将其添加到队列中。然后，我们按照代价的顺序从队列中取出节点，并将其标记为已访问。对于每个未访问的邻居节点，我们计算到该节点的新距离，并将其添加到队列中，以便在之后进行处理。

最后，我们输出每个节点的最短路径。在这个示例中，我们使用了一个优先队列来维护未访问的节点，以便在每个步骤中选择最小的距离节点。