个人中心
gpt4 book ai didi

java - Dijkstra 的全对最短路径

转载 作者：塔克拉玛干 更新时间：2023-11-03 05:35:03 30 4
gpt4 key购买 nike

<分区>

我搜索了 Dijkstra 的全对最短路径的 Java 实现。我找到了一个源最短路径的算法。我其实不懂Java，但我正在研究离散数学，所以也许有人可以帮助我。我必须改变什么才能使其成为全对最短路径？

------------编辑--------再次感谢 templatetypedef。我试试现在我认为代码中还有一个小错误。

输入文件(try.txt):

 0 2 68
 3 4 97
 0 3 8

这是我得到的错误输出:

    From 3:
Shortest Path Cost to 3 is: 0.0
Shortest Path Cost to 2 is: Infinity
Shortest Path Cost to 0 is: Infinity
Shortest Path Cost to 4 is: 97.0

From 2:
Shortest Path Cost to 3 is: Infinity
Shortest Path Cost to 2 is: 0.0
Shortest Path Cost to 0 is: Infinity
Shortest Path Cost to 4 is: 97.0

From 0:
Shortest Path Cost to 3 is: 8.0
Shortest Path Cost to 2 is: 68.0
Shortest Path Cost to 0 is: 0.0
Shortest Path Cost to 4 is: 97.0

From 4:
Shortest Path Cost to 3 is: 8.0
Shortest Path Cost to 2 is: 68.0
Shortest Path Cost to 0 is: Infinity
Shortest Path Cost to 4 is: 0.0

代码:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Vertex implements Comparable<Vertex> {
    public final String name;
    public List<Edge1> adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;

    public Vertex(String argName) {
        name = argName;
        adjacencies = new ArrayList<Edge1>();
    }

    public void addEdge(Edge1 e) {
        adjacencies.add(e);
    }

    public String toString() {
        return name;
    }

    public int compareTo(Vertex other) {
        return Double.compare(minDistance, other.minDistance);
    }

}

class Edge1{
    public final Vertex target;
    public final double weight;

    public Edge1(Vertex argTarget, double argWeight) {
        target = argTarget;
        weight = argWeight;
    }
}


public class Dijkstra {

    public static void computePaths(Vertex source) {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();

            // Visit each Edge exiting u

            for (Edge1 e : u.adjacencies) {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);
                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    vertexQueue.add(v);
                }

            }
        }
    }

    public static List<Vertex> getShortestPathTo(Vertex target) {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);

        Collections.reverse(path);
        return path;
    }

    public static void main(String args[]) {

        Map<String, Vertex> vertexMap = new HashMap<String, Vertex>();
        BufferedReader in = null;
        try {
            in = new BufferedReader(new FileReader("try.txt"));
            String line;
            boolean inVertex = true;

            while ((line = in.readLine()) != null) {


                    //store the edges
                    String[] parts = line.split(" ");
                    String vFrom = parts[0];
                    String vTo = parts[1];
                    if(!vertexMap.containsKey(vFrom))
                    {
                        Vertex v= new Vertex(vFrom);
                        vertexMap.put(vFrom, v);
                    }
                    if(!vertexMap.containsKey(vTo))
                    {
                        Vertex v1= new Vertex(vTo);
                        vertexMap.put(vTo, v1);
                    }


                    double weight = Double.parseDouble(parts[2]);
                    Vertex v = vertexMap.get(vFrom);
                    if (v != null) {
                        v.addEdge(new Edge1(vertexMap.get(vTo), weight));

                }
            }
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }
        finally{
            if(in!= null)
                try {
                    in.close();
                } catch (IOException ignore) {
                }
        }

        //get a list of all the vertices
        Collection<Vertex> vertices = vertexMap.values();

        //Vertex source = vertices.iterator().next();
        for(Vertex source:vertices){
        System.out.println("From " + source+":");
        computePaths(source);
        for (Vertex v : vertices) {
            System.out.println("Shortest Path Cost to " + v + " is: " + v.minDistance);
           // List<Vertex> path = getShortestPathTo(v);
          //  System.out.println("Path: " + path);
        }System.out.println();
        source.minDistance=Double.POSITIVE_INFINITY;
        source.previous=null;}
    }
}

30 4 0
文章推荐： java - 搜索一个词，然后在同一行返回一个数字或词
文章推荐： php - 洋红色。按位置对产品集合进行排序
文章推荐： php - Imagick SVG 到 JPG 错误无解码委托(delegate)
文章推荐： c# - 根据大小对数字范围进行分区，然后找到该范围内给定数字的分区起点
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com