JS实现单源点最短路径、动态规划分段图算法

simon_chen 发布于2019-08-21 18:28 / 1172人阅读

摘要：最近在上算法课大三，因为自己是写的，不想用去写。在网上百度用实现单源点最短路径动态规划分段图算法这两个算法，发现并没有。。。

最近在上算法课（大三），因为自己是写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云服务器云服务器最短路径算法程序最短路径算法大全最短路径算法合集最短路径算法简述

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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