最小距离相关算法

Dijkstra 算法 单源最短路径算法 路径大于零

1. 定义概览

Dijkstra(迪杰斯特拉) 算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

2. 算法步骤

2.1 算法思想

首先初始整个带权重的有向图 G =(N,E). 然后在将所有节点分成两个集合 S(表示已经算计完毕的节点，初始为发起节点，值为 0)、U(表示未确定的节点列表，初始为 除了初始节点之外的节点，值为无限大)。按照最短路径从 U 里面的节点移动到 S 里面，必须保证 U 中的任意节点到原始节点的距离大于 S 中的任意节点到原始节点的距离。

2.2 算法步骤

1. 初始化图，u 为原始节点、S 为已处理节点 {u=0}、U 未处理节点 {除了 u 其它节点 = 无限大}。将 u 设置为当前节点 `u
2. 遍历 U 里面所有节点到 `u 距离 `d，如果节点不与 `u 直连则 ` 为无限大。判断 U 里面的每个节点当前距离是否大于 `d + `u 到 u 的距离，大于就替换
3. 选择 U 里面节点的距离最小的节点，移动到 S。并将其设置为 `u
4. 重复 2，3 两个步骤，直到计算完所有节点。

2.3 算法可视化

3. 代码

3.1 java + guava

import com.google.common.graph.ImmutableValueGraph;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;
import lombok.extern.slf4j.Slf4j;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

@Slf4j
public class DijkstraTest {public static void main(String[] args) {
        // init
        MutableValueGraph<Integer, Integer> init = ValueGraphBuilder.undirected().build();

        init.putEdgeValue(1, 2, 7);
        init.putEdgeValue(2, 3, 10);
        init.putEdgeValue(1, 3, 9);
        init.putEdgeValue(1, 6, 14);
        init.putEdgeValue(2, 4, 15);
        init.putEdgeValue(3, 6, 2);
        init.putEdgeValue(3, 4, 11);
        init.putEdgeValue(6, 5, 9);
        init.putEdgeValue(5, 4, 6);
        ImmutableValueGraph<Integer, Integer> graph = ImmutableValueGraph.copyOf(init);


        //1.
        Map<Integer, Integer> S = new HashMap<>();
        Map<Integer, Integer> U = new HashMap<>();
        int u = 1;
        S.put(1, 0);
        for (int i = 2; i <= 6; i++) {U.put(i, Integer.MAX_VALUE);
        }

        // 2.
        for (; ;) {

            Integer finalU = u;
            graph.adjacentNodes(u).stream().filter(U::containsKey).forEach(node -> {Optional<Integer> value = graph.edgeValue(finalU, node);
                if (value.get() + S.get(finalU) < U.get(node)) {U.put(node, value.get());
                }
            });
            // 3.
            Optional<Map.Entry<Integer, Integer>> min = U.entrySet().stream().min(Comparator.comparing(Map.Entry::getValue));
            u = min.get().getKey();
            S.put(u, min.get().getValue());
            U.remove(u);
            log.info("{},{}", S, U);
            if (U.isEmpty()) {break;}
            // 4.
        }
        log.info("result {}", S);


    }
}