圖算法

chavesgu 發布于2019-08-19 10:29 / 3019人閱讀

摘要：最小距離相關算法算法單源最短路徑算法路徑大于零定義概覽迪杰斯特拉算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。注意該算法要求圖中不存在負權邊。算法可視化代碼

最小距離相關算法 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 算法步驟

初始化圖，u為原始節點、S為已處理節點{u=0}、U未處理節點{除了u其它節點=無限大}。將u設置為當前節點`u

遍歷U里面所有節點到`u 距離`d，如果節點不與`u直連則`為無限大。判斷U里面的每個節點當前距離是否大于 `d + `u到u的距離，大于就替換

選擇U里面節點的距離最小的節點，移動到S。并將其設置為 `u

重復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 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);


    }
}

云服務器 GPU云服務器圖算法二分圖集合算法圖算法 python java 圖搜索算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/76119.html

深度學習時代的目標檢測算法

摘要：目前目標檢測領域的深度學習方法主要分為兩類的目標檢測算法的目標檢測算法。原來多數的目標檢測算法都是只采用深層特征做預測，低層的特征語義信息比較少，但是目標位置準確高層的特征語義信息比較豐富，但是目標位置比較粗略。目前目標檢測領域的深度學習方法主要分為兩類：two stage的目標檢測算法；one stage的目標檢測算法。前者是先由算法生成一系列作為樣本的候選框，再通過卷積神經網絡進行樣本...

wfc_666 2019-04-25 18:24 評論0 收藏0
js數據結構和算法（四）圖和圖算法

摘要：分別被命名為和。圖的遍歷深度優先遍歷深度優先遍歷，也有稱為深度優先搜索，簡稱為。拓撲排序算法與類似，不同的是，拓撲排序算法不會立即輸出已訪問的頂點，而是訪問當前頂點鄰接表中的所有相鄰頂點，直到這個列表窮盡時，才會將當前頂點壓入棧中。圖的定義圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的...

Doyle 2019-08-21 10:22 評論0 收藏0
學習JavaScript數據結構與算法 — 圖

摘要：圖關聯矩陣在關聯矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖，頂點數是，邊的數量是，用鄰接矩陣表示圖需要的空間是，而使用關聯矩陣表示圖需要的空間是。廣度優先搜索算法數據結構是隊列。深度優先搜索算法數據結構是棧。定義圖和散列表、二叉樹一樣，是一種非線性數據結構。如圖1所示，圖由一系列頂點以及連接頂點的邊構成。由一條邊連接在一起的頂點成為相鄰頂點，比如A和B、A和D是相鄰的，而A和...

yiliang 2019-08-22 11:09 評論0 收藏0
Adobe提出深度摳圖：利用卷積網絡分離圖像前景與背景

摘要：在等機構新提出的論文中，其采用了大規模數據集與深度神經網絡學習圖像的自然結構，從而進一步分離圖像的前景與背景。一張手動摳圖的前景圖擁有簡單背景作為輸入。對于每一張測試圖像，按照降序從第列到第列顯示了度量下的排名結果排名到。摳圖，一直是一件體力活，它需要大量的操作與時間。而傳統摳圖算法主要是以色彩為特征分離前景與背景，并在小數據集上完成，而這就造成了傳統算法的局限性。在 Adobe 等機構新...

soasme 2019-04-25 18:10 評論0 收藏0