算法实现-Dijkstras

参考:最短路径问题---Dijkstra算法详解

image.png

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.experimental.Accessors;

import static java.util.Comparator.comparing;
import static java.util.stream.Collectors.groupingBy;

/**
 * Main
 *
 * @author youhl
 * @date 2018/12/17
 */
public class Main {
  /**
   * 图
   */
  static class Graph {
    private List<Vertex> topList = new ArrayList();
    private Map<Vertex, List<Edge>> edgeMap = new HashMap();

    public Graph addVertex(Vertex... vertexes) {
      topList.addAll(Arrays.asList(vertexes));
      return this;
    }

    public Graph addEdge(Vertex start, Vertex end, int weight) {
      Edge edge = new Edge(start, end, weight);
      List<Edge> list = edgeMap.get(start);
      if (list == null) {
        list = new ArrayList();
        edgeMap.put(start, list);
      }
      list.add(edge);
      return this;
    }

    public List<Dis> dijkstra(Vertex start) {
      List<Dis> disList = new ArrayList<>();
      Map<Vertex, Integer> minMap = new HashMap<>(16);
      edgeMap.getOrDefault(start, new ArrayList<>()).stream().forEach(e -> {
        Integer v = minMap.get(e.getEnd());
        minMap.put(e.getEnd(), Math.min(e.getWeight(), v == null ? e.getWeight() : v));
      });
      for (Vertex v : topList) {
        Dis dis = new Dis().setV(v).setDone(false).setPath(new ArrayList<>());
        if (v.equals(start)) {
          dis.dis = 0;
          dis.done = true;
        } else {
          dis.dis = minMap.getOrDefault(v, Integer.MAX_VALUE);
        }
        disList.add(dis);
      }
      for (; ; ) {
        Dis next = disList.stream().filter(d -> !d.done).min(comparing(Dis::getDis)).orElse(null);
        if (next == null) {
          break;
        }
        next.done = true;
        // 查找通过 next 中转的点
        List<Edge> edges = edgeMap.get(next.v);
        if (edges != null && next.dis < Integer.MAX_VALUE) {
          edges.stream().collect(groupingBy(Edge::getEnd)).forEach((k, v) -> {
            Dis dis = disList.stream().filter(c -> c.v.equals(k)).findFirst().get();
            Edge edge = v.stream().min(comparing(Edge::getWeight)).get();
            if (dis.dis > next.dis + edge.weight) {
              dis.dis = next.dis + edge.weight;
              dis.path.clear();
              dis.path.addAll(next.path);
              dis.path.add(edge);
            }
          });
        }
      }
      return disList;
    }
  }

  /**
   * 计算辅助类
   */
  @Accessors(chain = true)
  @Data
  static class Dis {
    Vertex v;
    int dis;
    List<Edge> path;
    boolean done;
  }


  /**
   * 顶点
   */
  @Data
  @AllArgsConstructor
  static class Vertex {
    public final String key;
  }

  /**
   * 路径
   */
  @Data
  @AllArgsConstructor
  static class Edge {
    public final Vertex start;
    public final Vertex end;
    public final int weight;
  }

  public static void main(String[] args) {
    Vertex V1 = new Vertex("V1");
    Vertex V2 = new Vertex("V2");
    Vertex V3 = new Vertex("V3");
    Vertex V4 = new Vertex("V4");
    Vertex V5 = new Vertex("V5");
    Vertex V6 = new Vertex("V6");
    Graph graph = new Graph();
    graph.addVertex(V1, V2, V3, V4, V5, V6);
    graph.addEdge(V1, V6, 100);
    graph.addEdge(V1, V5, 30);
    graph.addEdge(V1, V3, 10);
    graph.addEdge(V5, V6, 60);
    graph.addEdge(V5, V4, 20);
    graph.addEdge(V4, V6, 10);
    graph.addEdge(V2, V3, 5);
    graph.addEdge(V3, V4, 50);
    List<Dis> disList = graph.dijkstra(V1);
    System.out.println(
        Arrays.stream("起点  终点    最短路径    长度".split("\\s+")).collect(Collectors.joining("\t")));

    disList.forEach(dis -> System.out.println(String
        .format("%s\t%s\t%s\t%s", V1.getKey(), dis.getV().getKey(),
            dis.getPath().stream().map(e -> e.getEnd().getKey() + ":" + e.getWeight())
                .collect(Collectors.joining(",", "{", "}")),
            dis.getDis() == Integer.MAX_VALUE ? "∞" : dis.getDis())));
  }
}

image.png