圖算法

chavesgu 發(fā)布于2019-08-19 10:29 / 3013人閱讀

摘要：最小距離相關(guān)算法算法單源最短路徑算法路徑大于零定義概覽迪杰斯特拉算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。注意該算法要求圖中不存在負(fù)權(quán)邊。算法可視化代碼

最小距離相關(guān)算法 Dijkstra算法單源最短路徑算法路徑大于零 1.定義概覽

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。

問題描述：在無向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長(zhǎng)度為 w[i]，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短路徑。（單源最短路徑）

2.算法步驟 2.1 算法思想

首先初始整個(gè)帶權(quán)重的有向圖G=(N,E).然后在將所有節(jié)點(diǎn)分成兩個(gè)集合 S(表示已經(jīng)算計(jì)完畢的節(jié)點(diǎn)，初始為發(fā)起節(jié)點(diǎn)，值為0)、U(表示未確定的節(jié)點(diǎn)列表，初始為除了初始節(jié)點(diǎn)之外的節(jié)點(diǎn)，值為無限大)。按照最短路徑從U里面的節(jié)點(diǎn)移動(dòng)到S里面，必須保證U中的任意節(jié)點(diǎn)到原始節(jié)點(diǎn)的距離大于S中的任意節(jié)點(diǎn)到原始節(jié)點(diǎn)的距離。

2.2 算法步驟

初始化圖，u為原始節(jié)點(diǎn)、S為已處理節(jié)點(diǎn){u=0}、U未處理節(jié)點(diǎn){除了u其它節(jié)點(diǎn)=無限大}。將u設(shè)置為當(dāng)前節(jié)點(diǎn)`u

遍歷U里面所有節(jié)點(diǎn)到`u 距離`d，如果節(jié)點(diǎn)不與`u直連則`為無限大。判斷U里面的每個(gè)節(jié)點(diǎn)當(dāng)前距離是否大于 `d + `u到u的距離，大于就替換

選擇U里面節(jié)點(diǎn)的距離最小的節(jié)點(diǎn)，移動(dòng)到S。并將其設(shè)置為 `u

重復(fù)2，3 兩個(gè)步驟，直到計(jì)算完所有節(jié)點(diǎn)。

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 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 graph = ImmutableValueGraph.copyOf(init);


        //1.
        Map S = new HashMap<>();
        Map 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 value = graph.edgeValue(finalU, node);
                if (value.get() + S.get(finalU) < U.get(node)) {
                    U.put(node, value.get());
                }
            });
            // 3.
            Optional> 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);


    }
}