【代码随想录Day58】图论Part09

dijkstra（堆优化版）精讲

题目链接/文章讲解：代码随想录

importjava.util.*;classEdge{intto;// 邻接顶点int val;// 边的权重Edge(intto,int val){this.to=to;this.val = val;}}classPair<U,V>{publicfinalU first;// 节点publicfinalV second;// 从源点到该节点的权重publicPair(U first,V second){this.first = first;this.second = second;}}publicclassMain{publicstaticvoidmain(String[] args){Scanner scanner =newScanner(System.in);// 读取节点数和边数int n = scanner.nextInt();int m = scanner.nextInt();// 创建图的邻接表List<List<Edge>> graph =newArrayList<>(n +1);for(int i =0; i <= n; i++){
            graph.add(newArrayList<>());}// 读取边的信息for(int i =0; i < m; i++){int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();
            graph.get(p1).add(newEdge(p2, val));}int start =1;// 起点int end = n;// 终点// 存储从源点到每个节点的最短距离int[] minDist =newint[n +1];Arrays.fill(minDist,Integer.MAX_VALUE);
        minDist[start]=0;// 起始点到自身的距离为0// 记录顶点是否被访问过boolean[] visited =newboolean[n +1];// 优先队列，用于选择当前最短路径的节点PriorityQueue<Pair<Integer,Integer>> pq =newPriorityQueue<>(Comparator.comparingInt(pair -> pair.second));// 初始化队列，添加源点
        pq.add(newPair<>(start,0));while(!pq.isEmpty()){// 取出当前距离源点最近的节点Pair<Integer,Integer> cur = pq.poll();int currentNode = cur.first;// 如果该节点已被访问，跳过if(visited[currentNode])continue;// 标记该节点为已访问
            visited[currentNode]=true;// 更新与当前节点相连的邻接节点的路径for(Edge edge : graph.get(currentNode)){// 如果该邻接节点未被访问且新路径更短，则更新最短路径if(!visited[edge.to]&& minDist[currentNode]+ edge.val < minDist[edge.to]){
                    minDist[edge.to]= minDist[currentNode]+ edge.val;
                    pq.add(newPair<>(edge.to, minDist[edge.to]));// 将新路径加入优先队列}}}// 输出结果System.out.println(minDist[end]==Integer.MAX_VALUE ?-1: minDist[end]);}}

Bellman_ford 算法精讲

题目链接/文章讲解：代码随想录

importjava.util.*;publicclassMain{// 定义边的内部类staticclassEdge{int from;// 起始节点intto;// 结束节点int val;// 边的权重publicEdge(int from,intto,int val){this.from = from;this.to=to;this.val = val;}}publicstaticvoidmain(String[] args){// 输入处理Scanner scanner =newScanner(System.in);int numberOfNodes = scanner.nextInt();// 节点数量int numberOfEdges = scanner.nextInt();// 边的数量List<Edge> edges =newArrayList<>();// 读取每一条边的信息for(int i =0; i < numberOfEdges; i++){int from = scanner.nextInt();intto= scanner.nextInt();int val = scanner.nextInt();
            edges.add(newEdge(from,to, val));}// 存储从起点到各节点的最小距离int[] minDistance =newint[numberOfNodes +1];Arrays.fill(minDistance,Integer.MAX_VALUE);// 初始化最小距离为无穷大
        minDistance[1]=0;// 起点到自身的距离为0// 执行 Bellman-Ford 算法，放松所有边 n-1 次for(int i =1; i < numberOfNodes; i++){for(Edge edge : edges){// 如果起始节点的距离不为无穷大，且通过当前边可以找到更短的路径if(minDistance[edge.from]!=Integer.MAX_VALUE){int newDistance = minDistance[edge.from]+ edge.val;if(newDistance < minDistance[edge.to]){
                        minDistance[edge.to]= newDistance;// 更新最小距离}}}}// 输出结果if(minDistance[numberOfNodes]==Integer.MAX_VALUE){System.out.println("unconnected");// 如果目标节点不可达}else{System.out.println(minDistance[numberOfNodes]);// 输出目标节点的最小距离}

        scanner.close();// 关闭扫描器以释放资源}}