成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

JS實(shí)現(xiàn)單源點(diǎn)最短路徑、動態(tài)規(guī)劃分段圖算法

simon_chen / 1247人閱讀

摘要：最近在上算法課大三，因?yàn)樽约菏菍懙?，不想用去寫。在網(wǎng)上百度用實(shí)現(xiàn)單源點(diǎn)最短路徑動態(tài)規(guī)劃分段圖算法這兩個(gè)算法，發(fā)現(xiàn)并沒有。。。

最近在上算法課（大三），因?yàn)樽约菏菍慾s+php的，不想用c去寫。在網(wǎng)上百度用js實(shí)現(xiàn)單源點(diǎn)最短路徑、動態(tài)規(guī)劃分段圖算法這兩個(gè)算法，發(fā)現(xiàn)并沒有。。。于是自己xjb寫了下，c里的帶指針的結(jié)構(gòu)體按我的理解換成了對象數(shù)組，寫的不好請各位大牛給點(diǎn)改進(jìn)的建議。。。

動態(tài)規(guī)劃 
    function createPoint(next,len,section){

        var o=new Object();

        o.next=next;

        o.len=len;

        o.section=section;

        return o;

    }



    var v1=createPoint([2,3,4,5],[9,7,3,2],1);

    var v2=createPoint([6,7,8],[4,2,1],2);

    var v3=createPoint([6,7],[2,7],2);

    var v4=createPoint([8],[11],2);

    var v5=createPoint([7,8],[11,8],2);

    var v6=createPoint([9,10],[6,5],3);

    var v7=createPoint([9,10],[4,3],3);

    var v8=createPoint([10,11],[5,6],3);

    var v9=createPoint([12],[4],4);

    var v10=createPoint([12],[2],4);

    var v11=createPoint([12],[5],4);

    var v12=createPoint([],[],5);



    var MAX=10000;

    function main(points,max_section) {

        //定義一個(gè)二維數(shù)組COST,如COST[4][9]表示第4段的v9這個(gè)點(diǎn)到終點(diǎn)的最短距離

        var COST = new Array();

        for(var k=0;k0){

            for(i=0;i

這是上面的圖，這篇文章里的http://blog.csdn.net/ncepuzhu...

單源點(diǎn)最短路徑

    function createPoint(next,len){

        var o=new Object();

        o.next=next;

        o.len=len;

        return o;

    }


    function indexMin(arr) {

        var min = Math.min.apply(null,arr);

        //dist數(shù)組里的最小值的下標(biāo)，即v幾

        return arr.indexOf(min);

    }

    var v0=createPoint([1,2,3],[20,50,30]);

    var v1=createPoint([2,5],[25,70]);

    var v2=createPoint([4,5],[25,50]);

    var v3=createPoint([4],[55]);

    var v4=createPoint([5,6],[10,70]);

    var v5=createPoint([6],[50]);

    var v6=createPoint([],[]);



    var nodes=[v0,v1,v2,v3,v4,v5,v6];

    var MAX=10000;

    //nodes為點(diǎn)集合

    function dijkstra(nodes){

        var dist=Array.apply(null, Array(nodes.length)).map(() => MAX)

        //s為已選取的結(jié)點(diǎn)集合 0表示還不在 1表示在

        var s=Array.apply(null,Array(nodes.length)).map(()=>0);

        s[0]=1;

        var i,min;

        //從源點(diǎn)v0出發(fā)，選個(gè)最短的路徑

        //先判斷源點(diǎn)是否與其他點(diǎn)相鄰接

        if (nodes[0].next===undefined||nodes[0].next==0){

            console.log("源點(diǎn)沒有鄰接點(diǎn)");

            return;

        }



        for (i=0;i MAX);

            for (i=0;i

本來想用矩陣（二維數(shù)組）來存儲圖的，但是想到每次都要循環(huán)找數(shù)，似乎有點(diǎn)麻煩。就用這樣的對象數(shù)組了

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

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

相關(guān)文章

  • 單源點(diǎn)最短路徑(Bellman-Ford)原理及js實(shí)現(xiàn)

    摘要：說明算法運(yùn)行結(jié)束后，會得到從源節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路徑，同時(shí)得到每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，不能包含負(fù)權(quán)回路如圖但可以包含圖，這里所說的負(fù)權(quán)環(huán)路是指環(huán)路的權(quán)值總和為正或?yàn)樨?fù)圖圖松弛操作概念松弛操作針對的操作對象是圖中的邊，對圖中任意一條邊， 1. 說明 Bellman-Ford算法運(yùn)行結(jié)束后，會得到從源節(jié)點(diǎn) s 到其它所有節(jié)點(diǎn)的最短路徑，同時(shí)得到每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，Bellman-Ford...

    Michael_Lin 評論0 收藏0

  • 王者編程大賽之五 — 最短路徑

    摘要：由于是從頂點(diǎn)到的最短路徑，則有。算法流程根據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)，提出了以最短路徑長度遞增，逐次生成最短路徑的算法。相關(guān)文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環(huán) 首發(fā)于 樊浩柏科學(xué)院 自如年底就會擁有 50W 間房子，大家知道每間房房子都是需要配置完才能出租給自如客的，整個(gè)房租的配置過程是很復(fù)雜的，每天都需要大量的物流師傅將家電、家具...

    yuanzhanghu 評論0 收藏0

  • 面試算法實(shí)踐與國外大廠習(xí)題指南

    摘要：面試算法實(shí)踐與國外大廠習(xí)題指南翻譯自維護(hù)的倉庫，包含了在線練習(xí)算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。面試算法實(shí)踐與國外大廠習(xí)題指南在線練習(xí)在線面試編程數(shù)據(jù)結(jié)構(gòu)鏈表即是由節(jié)點(diǎn)組成的線性集合，每個(gè)節(jié)點(diǎn)可以利用指針指向其他節(jié)點(diǎn)。 面試算法實(shí)踐與國外大廠習(xí)題指南 翻譯自 Kevin Naughton Jr. 維護(hù)的倉庫 interviews，包含了在線練習(xí)、算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和...

    genedna 評論0 收藏0

  • 基于Segment Routing技術(shù)構(gòu)建新一代骨干網(wǎng)：智能、可靠、可調(diào)度（一）

    摘要：為了解決骨干網(wǎng)當(dāng)前的問題，基礎(chǔ)網(wǎng)絡(luò)團(tuán)隊(duì)在年下半年開始，對新一代骨干網(wǎng)架構(gòu)進(jìn)行重新設(shè)計(jì)硬件選型，在新一代骨干網(wǎng)架構(gòu)設(shè)計(jì)中采用了當(dāng)前比較流行的源路由即技術(shù)以下簡稱，在介紹新一代骨干網(wǎng)架構(gòu)之前先給大家簡單介紹一下技術(shù)的基本概念。前言隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和云計(jì)算業(yè)務(wù)的快速普及，當(dāng)前各行各業(yè)的客戶都有迫切上云的需求，越來越多的關(guān)鍵業(yè)務(wù)，如：web前端、視頻會議、辦公應(yīng)用、數(shù)據(jù)存儲等開始部署在云端；新的網(wǎng)...

    Tecode 評論0 收藏0

發(fā)表評論

0條評論

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