dijkstra算法有向图java

### 关于Dijkstra算法在Java中有向图上的实现

对于有向图而言，在Java中实现Dijkstra算法可以采用优先队列来优化节点的选择过程，从而提高效率。下面是一个基于邻接表表示法的简单例子[^1]：

import java.util.*;

public class DijkstraAlgorithm {
    static final int INFINITY = Integer.MAX_VALUE;
    
    public static void dijkstra(int[][] graph, int startNode, int[] distances){
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));
        boolean[] visitedNodes = new boolean[graph.length];
        
        Arrays.fill(distances, INFINITY);
        distances[startNode] = 0;
        priorityQueue.add(new Node(startNode, 0));

        while (!priorityQueue.isEmpty()){
            Node currentNode = priorityQueue.poll();
            
            if (visitedNodes[currentNode.index]){
                continue;
            }
            visitedNodes[currentNode.index] = true;

            for (int i = 0; i < graph.length; ++i){
                if(graph[currentNode.index][i]!=0 && !visitedNodes[i]){
                    int potentialDistance = distances[currentNode.index]+graph[currentNode.index][i];

                    if(potentialDistance<distances[i]){
                        distances[i]=potentialDistance;
                        priorityQueue.offer(new Node(i,potentialDistance));
                    }
                }
            }
        }
    }

    private static class Node{
        int index,distance;

        public Node(int index,int distance){
            this.index=index;
            this.distance=distance;
        }
    }

    // 测试函数
    public static void main(String args[]){
        /* 创建测试用例 */
        int V = 5;
        int[][] graph = {{0,9,75,0,0},
                         {9,0,95,19,42},
                         {75,95,0,51,66},
                         {0,19,51,0,31},
                         {0,42,66,31,0}};
                         
        int[] distances=new int[V];
        dijkstra(graph,0,distances);

        System.out.println("Vertex\t Distance from Source");
        for (int i=0;i<V;++i)
           System.out.printf("%d \t %d\n",i,distances[i]);
    }
}

此程序定义了一个`dijkstra()`方法接收三个参数：一个是代表加权有向图的二维数组；另一个是指定起始顶点索引；最后一个是用来存储从起点到达各个顶点最小距离的一维整型数组。

在这个版本里，如果两个顶点之间不存在直接连接，则对应的矩阵元素被设置成零。此外，为了简化问题描述，这里假设输入的是稠密图形式的数据结构——即使用完整的V×V大小的方阵作为输入数据格式(V为顶点数量)，即使实际应用中可能更倾向于稀疏图表达方式（比如链式前向星）。当面对大规模稀疏网络时，建议考虑改用更加节省空间的方法来进行编码。