亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

圖算法

chavesgu / 3065人閱讀

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

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

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

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

2.算法步驟 2.1 算法思想

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

2.2 算法步驟

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

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

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

重復(fù)2，3 兩個步驟，直到計算完所有節(jié)點。

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


    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/76119.html

相關(guān)文章

  • 深度學(xué)習(xí)時代的目標(biāo)檢測算法

    摘要：目前目標(biāo)檢測領(lǐng)域的深度學(xué)習(xí)方法主要分為兩類的目標(biāo)檢測算法的目標(biāo)檢測算法。原來多數(shù)的目標(biāo)檢測算法都是只采用深層特征做預(yù)測，低層的特征語義信息比較少，但是目標(biāo)位置準(zhǔn)確高層的特征語義信息比較豐富，但是目標(biāo)位置比較粗略。 目前目標(biāo)檢測領(lǐng)域的深度學(xué)習(xí)方法主要分為兩類：two stage的目標(biāo)檢測算法；one stage的目標(biāo)檢測算法。前者是先由算法生成一系列作為樣本的候選框，再通過卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行樣本...

    wfc_666 評論0 收藏0

  • js數(shù)據(jù)結(jié)構(gòu)和算法（四）圖和圖算法

    摘要：分別被命名為和。圖的遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷，也有稱為深度優(yōu)先搜索，簡稱為。拓?fù)渑判蛩惴ㄅc類似，不同的是，拓?fù)渑判蛩惴ú粫⒓摧敵鲆言L問的頂點，而是訪問當(dāng)前頂點鄰接表中的所有相鄰頂點，直到這個列表窮盡時，才會將當(dāng)前頂點壓入棧中。 圖的定義 圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的...

    Doyle 評論0 收藏0

  • 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 圖

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

    yiliang 評論0 收藏0

  • Adobe提出深度摳圖：利用卷積網(wǎng)絡(luò)分離圖像前景與背景

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

    soasme 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<