JS實現單源點最短路徑、動態規劃分段圖算法

simon_chen 發布于2019-08-21 18:28 / 1212人閱讀

摘要：最近在上算法課大三，因為自己是寫的，不想用去寫。在網上百度用實現單源點最短路徑動態規劃分段圖算法這兩個算法，發現并沒有。。。

最近在上算法課（大三），因為自己是寫js+php的，不想用c去寫。在網上百度用js實現單源點最短路徑、動態規劃分段圖算法這兩個算法，發現并沒有。。。于是自己xjb寫了下，c里的帶指針的結構體按我的理解換成了對象數組，寫的不好請各位大牛給點改進的建議。。。

動態規劃

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

        //定義一個二維數組COST,如COST[4][9]表示第4段的v9這個點到終點的最短距離

        var COST = new Array();

        for(var k=0;k0){

            for(i=0;i

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

單源點最短路徑
    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數組里的最小值的下標，即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為點集合

    function dijkstra(nodes){

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

        //s為已選取的結點集合 0表示還不在 1表示在

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

        s[0]=1;

        var i,min;

        //從源點v0出發，選個最短的路徑

        //先判斷源點是否與其他點相鄰接

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

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

            return;

        }



        for (i=0;i MAX);

            for (i=0;i
本來想用矩陣（二維數組）來存儲圖的，但是想到每次都要循環找數，似乎有點麻煩。就用這樣的對象數組了

云服務器 GPU云服務器最短路徑算法程序最短路徑算法大全最短路徑算法合集最短路徑算法簡述

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

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

單源點最短路徑(Bellman-Ford)原理及js實現

摘要：說明算法運行結束后，會得到從源節點到其它所有節點的最短路徑，同時得到每個節點的前驅節點，不能包含負權回路如圖但可以包含圖，這里所說的負權環路是指環路的權值總和為正或為負圖圖松弛操作概念松弛操作針對的操作對象是圖中的邊，對圖中任意一條邊， 1. 說明 Bellman-Ford算法運行結束后，會得到從源節點 s 到其它所有節點的最短路徑，同時得到每個節點的前驅節點，Bellman-Ford...

Michael_Lin 2019-08-21 18:37 評論0 收藏0
王者編程大賽之五 — 最短路徑

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

yuanzhanghu 2019-07-01 12:36 評論0 收藏0
面試算法實踐與國外大廠習題指南

摘要：面試算法實踐與國外大廠習題指南翻譯自維護的倉庫，包含了在線練習算法概述與大廠習題實戰等內容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數據結構鏈表即是由節點組成的線性集合，每個節點可以利用指針指向其他節點。面試算法實踐與國外大廠習題指南翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews，包含了在線練習、算法概述與大廠習題實戰等內容。筆者發現正好和...

genedna 2019-08-14 17:46 評論0 收藏0
基于Segment Routing技術構建新一代骨干網：智能、可靠、可調度（一）

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

Tecode 2022-06-28 18:59 評論0 收藏0