基于Dijkstra算法，实现求城市之间最短距离

源代码存放在git，其中还有其他算法实现：https://github.com/zhangpei

git地址bisha/dataStructure.git

https://github.com/zhangpeibisha/dataStructure.git

https://github.com/zhangpeibisha/dataStructure.git

https://github.com/zhangpeibisha/dataStructure.git

https://github.com/zhangpeibisha/dataStructure.git

dijkstra算法简单思想：

1.使用两个集合，一个存已经遍历了的节点，一个存还未遍历的节点。集合格式{U（10）}代表起点到U节点距离为10

2.基于广度遍历

3.求解两步走：

第一步，找到还未访问节点，且其中最短路径的节点，并将这个最短路径存入已经遍历的节点。

第二部，通过找到的最短路径节点，去修正其他为访问节点到起点的最短路径。

上代码：

city类：

import java.util.ArrayList;
import java.util.List;

/**
 * Create by [email protected] on 2018/4/22.
 */
public class City {

    // 城市名字
    private String cityName;

    // 与该城市邻接的城市
    private List<Distance> distance;

    public City() {
        init();
    }

    /**
     * 初始化这个对象，因为当前城市到当前城市的距离默认为0
     */
    public void init() {
        distance = new ArrayList<>();
        distance.add(new Distance(this, this, 0.0));
    }

    public String getCityName() {
        return cityName;
    }

    public void setCityName(String cityName) {
        this.cityName = cityName;
    }

    public List<Distance> getDistance() {
        return distance;
    }

    public void setDistance(List<Distance> distance) {
        this.distance = distance;
    }

    public City addDistance(City toCity) {
        this.distance.add(new Distance(this, toCity));
        return this;
    }

    public City addDistance(City toCity, double distance) {
        this.distance.add(new Distance(this, toCity, distance));
        return this;
    }


}

Distance类：

/**
 * Create by [email protected] on 2018/4/22.
 *
 * 此为原始路径距离
 */
public class Distance {

    // 起点城市
    private City fromCity;

    // 目的城市
    private City toCity;

    // 两个城市之间的距离  为空则为无穷大
    private double distance = Integer.MAX_VALUE-1;

    public Distance(City fromCity, City toCity) {
        this.fromCity = fromCity;
        this.toCity = toCity;
    }

    public Distance(City fromCity, City toCity, double distance) {
        this.fromCity = fromCity;
        this.toCity = toCity;
        this.distance = distance;
    }

    public City getFromCity() {
        return fromCity;
    }

    public void setFromCity(City fromCity) {
        this.fromCity = fromCity;
    }

    public City getToCity() {
        return toCity;
    }

    public void setToCity(City toCity) {
        this.toCity = toCity;
    }

    public Double getDistance() {
        return distance;
    }

    public void setDistance(Double distance) {
        this.distance = distance;
    }
}

ShortPath类：

/**
 * Create by [email protected] on 2018/4/22.
 *
 * 城市与城市之间的最短路径
 */
public class ShortPath {

    // 出发城市
    private City fromCity;

    // 目的城市
    private City toCity;

    // 途径地
    private Queue<City> ways;

    // 两个城市之间的需要走的距离
    private Double distance;

    public ShortPath(City fromCity, City toCity) {
        this.fromCity = fromCity;
        this.toCity = toCity;
    }

    public City getFromCity() {
        return fromCity;
    }

    public void setFromCity(City fromCity) {
        this.fromCity = fromCity;
    }

    public City getToCity() {
        return toCity;
    }

    public void setToCity(City toCity) {
        this.toCity = toCity;
    }

    public Queue<City> getWays() {
        return ways;
    }

    public void setWays(Queue<City> ways) {
        this.ways = ways;
    }

    public Double getDistance() {
        return distance;
    }

    public void setDistance(Double distance) {
        this.distance = distance;
    }
}

Dijkstra类：

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Create by [email protected] on 2018/4/22.
 * <p>
 * 具体算法
 */
public class CityDijKstra {

    // 起点城市
    private final City startCity;

    private final City endCity;

    // 使用邻接矩阵表示地图
    private List<City> map;

    // 求出来的最短路径结果保存，若为空则没有路径可达
    private ShortPath shortPath;

    public CityDijKstra(City startCity, City endCity, List<City> map) {
        this.startCity = startCity;
        this.endCity = endCity;
        this.map = map;
        init();
    }

    private void dijkstra(int citySize, int startIndex, int endIndex) {

        // 保存起点城市到其他城市的最短长度
        double[] shortPath = new double[citySize];
        // 标记城市是否被求的最短路径
        boolean[] marked = new boolean[citySize];
        // 保存最短路径访问
        Queue<City>[] paths = new LinkedList[citySize];
        // 起点和其他点的距离
        List<Distance> startDistance = map.get(startIndex).getDistance();

        //初始化paths
        for (int i = 0; i < citySize; i++) {
            Queue<City> queue = new LinkedList<>();
            queue.offer(startCity);
            queue.offer(map.get(i));
            paths[i] = queue;
        }

        // 自己访问自己距离为0 且不必在求最短路径，因此标记为true
        shortPath[startIndex] = 0;
        marked[startIndex] = true;

        for (int i = 1; i < citySize; i++) {

            /**
             * 此部分计算起点到其他为标记点中最短路径的那个点
             */
            // 记录顶点能到达点的最短距离的下标
            int k = -1;
            // 距离为Integer.MAX_VALUE表示不可达
            double mind = Integer.MAX_VALUE;

            for (int j = 0; j < citySize; j++) {

                double dis = startDistance.get(j).getDistance();

                if (!marked[j] && dis < mind) {
                    mind = dis;
                    k = j;
                }
            }

            shortPath[k] = mind;
            marked[k] = true;

            /**
             * 此部分根据k点修正起点到其他所有节点的前驱节点及距离
             */

            for (int j = 0; j < citySize; j++) {

                //起点到k点的最短距离 + k点到j点的最短距离
                double dis = startDistance.get(k).getDistance() +
                        map.get(k).getDistance().get(j).getDistance();

                // 判断j点是否被标记，若没有被标记，且dis小于直达距离，则修正最短距离
                if (!marked[j] && dis < startDistance.get(j).getDistance()) {

                    map.get(startIndex)
                            .getDistance()
                            .get(j).setDistance(dis);

                    Queue<City> queue = new LinkedList<>();
                    for (City city : paths[k]) {
                        queue.offer(city);
                    }
                    queue.offer(map.get(j));
                    paths[j] = queue;
                }
            }
        }
        display(shortPath, paths);
        this.shortPath.setDistance(shortPath[endIndex]);
        this.shortPath.setWays(paths[endIndex]);
    }


    private void init() {
        // 初始化最短路径结果中的起始城市和目的城市
        shortPath = new ShortPath(startCity, endCity);
        int citySize = map.size();
        int startIndex = map.indexOf(startCity);
        int endIndex = map.indexOf(endCity);
        dijkstra(citySize, startIndex, endIndex);
        display(map);
    }

    private void display(double[] dis, Queue<City>[] paths) {

        for (int i = 0; i < dis.length; i++) {
            System.out.print(startCity.getCityName() + "到" + map.get(i).getCityName());
            System.out.print("的距离为：" + dis[i]);
            System.out.println();
            System.out.print(startCity.getCityName() + "到" + map.get(i).getCityName());
            System.out.print("的路径为：");
            for (City city : paths[i]) {
                System.out.print(city.getCityName() + " ");
            }
            System.out.println();
        }
    }

    private void display(List<City> cities){
        System.out.println("==========================");
        for (City city : cities) {
            for (int i = 0; i <city.getDistance().size() ; i++) {
                System.out.print(city.getCityName() + "到");
                if (city.getDistance().get(i).getDistance() < Integer.MAX_VALUE/2)
                System.out.print(city.getDistance().get(i).getToCity().getCityName() +
                        "距离为" +
                        city.getDistance().get(i).getDistance());
                else
                    System.out.print(city.getDistance().get(i).getToCity().getCityName() +
                            "距离为不可达");
                System.out.println();
            }

        }
    }
}

测试类：ShortPahtTest:

import java.util.ArrayList;
import java.util.List;

/**
 * Create by [email protected] on 2018/4/22.
 * <p>
 * 最短路径算法测试
 */
public class ShortPathTest {

    public static void main(String[] args) {

        double MAX = Integer.MAX_VALUE;

        City chongqing = new City();
        chongqing.setCityName("重庆0");

        City guangzhou = new City();
        guangzhou.setCityName("广州1");

        City shenzheng = new City();
        shenzheng.setCityName("深圳2");

        City huizhou = new City();
        huizhou.setCityName("惠州3");

        City shanghai = new City();
        shanghai.setCityName("上海4");


        chongqing.addDistance(guangzhou,10.0)
                .addDistance(shenzheng)
                .addDistance(huizhou,30.0)
                .addDistance(shanghai,100.0);

        guangzhou.addDistance(chongqing)
                .addDistance(shenzheng,50.0)
                .addDistance(huizhou)
                .addDistance(shanghai);

        shenzheng.addDistance(guangzhou)
                .addDistance(chongqing)
                .addDistance(huizhou)
                .addDistance(shanghai,10.0);

        huizhou.addDistance(guangzhou)
                .addDistance(shenzheng,20.0)
                .addDistance(chongqing)
                .addDistance(shanghai,60.0);

        shanghai.addDistance(guangzhou)
                .addDistance(shenzheng)
                .addDistance(huizhou)
                .addDistance(chongqing);

        List<City> cities = new ArrayList<City>();
        cities.add(chongqing);
        cities.add(guangzhou);
        cities.add(shenzheng);
        cities.add(huizhou);
        cities.add(shanghai);

        CityDijKstra cityDijKstra = new CityDijKstra(chongqing,shenzheng,cities);
    }

}