详解Java如何实现FP-Growth算法

FP-Growth算法的Java实现

这篇文章重点讲一下实现。需要两次扫描来构建FP树

第一次扫描

第一次扫描,过滤掉所有不满足最小支持度的项;对于满足最小支持度的项,按照全局支持度降序排序。

按照这个需求,可能的难点为如何按照全局支持度对每个事务中的item排序。

我的实现思路

  • 扫描原数据集将其保存在二维列表sourceData中
  • 维护一个Table,使其保存每个item的全局支持度TotalSup
  • 在Table中过滤掉低于阈值minSup的项
  • 将Table转换为List,并使其按照TotalSup降序排序
  • 新建一个二维列表freqSource,其保留sourceData中的频繁项,并将每个事务按全局支持度降序排序

代码

/**
     * 扫描原数据集,生成事务集
     * @param path 数据集路径
     * @throws IOException
     */

    private void scanDataSet(String path) throws IOException {
        if(path.equals("")){
            path = filePath;
        }
        FileReader fr = new FileReader(path);
        BufferedReader bufferedReader = new BufferedReader(fr);
        String str;
//        int maxLength = 0;
        while ( (str = bufferedReader.readLine())!=null){
            ArrayList<Integer> transaction = new ArrayList<>();
            String[] tempEntry ;
            tempEntry = str.split(" ");
            for(int i =0;i< tempEntry.length;i++){
                if(!tempEntry[i].equals("")){
                    int itemValue = Integer.parseInt(tempEntry[i]);
                    transaction.add(itemValue);
                    if(!similarSingleItemLinkedListHeadsTable.containsKey(itemValue)){
                        similarSingleItemLinkedListHeadsTable.put(itemValue, new SimilarSingleItemLinkedListHead(itemValue,null,1));
                    }else{
                        //将该项的全局支持度+1
                        similarSingleItemLinkedListHeadsTable.get(itemValue).addSupTotal();
                    }
                }
            }
//            if(tempEntry.length>maxLength){
//                maxLength = tempEntry.length;
//            }

            sourceDataSet.add(transaction);

        }
//        System.out.println(maxLength);
        deleteNonFreqInSSILLHTAndSort();
        deleteNonFreqInSDSAndSort();
        bufferedReader.close();
        fr.close();
    }
        /**
     * 去除相似项表(similarSingleItemLinkedListHeadsTable)的非频繁项,并按全局支持度对similarSingleItemLinkedListHeads降序排序
     */
    private void deleteNonFreqInSSILLHTAndSort() {
        Hashtable<Integer,SimilarSingleItemLinkedListHead> copyOfSSILLHT =
                (Hashtable<Integer, SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeadsTable.clone();
        Set<Integer> keySet = copyOfSSILLHT.keySet();
        //删除非频繁项
        for(int key: keySet){
            if(similarSingleItemLinkedListHeadsTable.get(key).getSupTotal()<minSupCnt){//低于支持度阈值
                similarSingleItemLinkedListHeadsTable.remove(key);
            }
        }
        //按全局支持度排序
        similarSingleItemLinkedListHeadList = new ArrayList<>(similarSingleItemLinkedListHeadsTable.values());
        similarSingleItemLinkedListHeadList.sort(new Comparator<SimilarSingleItemLinkedListHead>() {
            @Override
            public int compare(SimilarSingleItemLinkedListHead o1, SimilarSingleItemLinkedListHead o2) {
                return o2.getSupTotal() - o1.getSupTotal();
            }
        });

    }
        /**
     * 去除事务集(sourceDataSet)的非频繁项,并且按全局支持度对每个事务的item进行降序排序
     * 其结果保存在freqSourceSortedDataSet
     */
    private void deleteNonFreqInSDSAndSort(){
        freqSourceSortedDataSet = (ArrayList<ArrayList<Integer>>) sourceDataSet.clone();
        for(int i =0;i<sourceDataSet.size();i++){
            for(int j = 0;j<sourceDataSet.get(i).size();j++){
                int item = sourceDataSet.get(i).get(j);
                // 由于此时SSILLHT里的项都是频繁项,只需要确定item是否存在在其中即可,存在即代表频繁.
                if(visitSupTotal(item)==-1){
                    //将非频繁项标记为最小整数值
                    freqSourceSortedDataSet.get(i).set(j,Integer.MIN_VALUE);
                }
            }
            //将标记的项移除.
            freqSourceSortedDataSet.get(i).removeIf(e->e == Integer.MIN_VALUE);
            insertSort(freqSourceSortedDataSet.get(i));
        }
        freqSourceSortedDataSet.removeIf(e->e.size() == 0);

    }

第二次扫描

第二次扫描,构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息

这里比较简单,因为已经有过滤、排序好的数据freqSourceSortedDataSet。我们只需要

  • 遍历freqSourceSortedDataSet的每一个事务trans,遍历trans中的每一个item构建FP树和相似项链表
  • 如果某item第一次遇到,则需要创建该节点并在相似项链表中链接它。
  • 链表不用多说。
  • 这里的FP树的子节点是不定个数的,需要用特殊的数据结构。我这里使用了HashTable
  /**
     * 构建FP树
     */
    private void buildFPTree(){
        for(ArrayList<Integer>trans:freqSourceSortedDataSet){
            Node curTreeNode = fpTree.root;
            for(int item :trans){
                if(!curTreeNode.children.containsKey(item)){
                    Node node = new Node(item,1);
                    curTreeNode.children.put(item,node);
                    node.father = curTreeNode;
                    buildSimilarSingleItemLinkedList(item,curTreeNode);
                }else{
                    curTreeNode.children.get(item).sup++;
                }
                curTreeNode=curTreeNode.children.get(item);
            }
        }
    }
    /**
     * 构建相似项链表
     */
    private void buildSimilarSingleItemLinkedList(int item,Node curTreeNode){
        //找到该item在相似项链表中的位置

        int index = searchForItemInHeadsList(item,
                (ArrayList<SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeadList);
        if(similarSingleItemLinkedListHeadList.get(index).next == null){
            similarSingleItemLinkedListHeadList.get(index).next = curTreeNode.children.get(item);
        }else{
            Node visitNode = similarSingleItemLinkedListHeadList.get(index).next;
            while (visitNode.nextSimilar!=null){

                visitNode = visitNode.nextSimilar;
            }
            if(visitNode != curTreeNode.children.get(item))
                visitNode.nextSimilar = curTreeNode.children.get(item);
        }
    }
    /**
     * 在HeadList中搜索某项的位置
     * @param item 项
     * @param similarSingleItemLinkedListHeads 头结点链表
     * @return 位置,-1表示未找到
     */
    private int searchForItemInHeadsList(int item, ArrayList<SimilarSingleItemLinkedListHead> similarSingleItemLinkedListHeads) {
        for(int i =0;i<similarSingleItemLinkedListHeads.size();i++){
            if(similarSingleItemLinkedListHeads.get(i).getItemValue() == item){
                return i;
            }
        }
        return -1;
    }

挖掘频繁项集

这一部分个人觉得是实现上最困难的部分。但是我在B站或其他地方一涉及到这个地方都讲得很快(B站也没两个视频讲这玩意儿,吐)。还有不同的概念,比如在黑皮书上讲的是前缀路径,在其他地方有条件模式基等概念。接下来的代码均按照前缀路径的说法来实现。

我们来捋一捋思路,挖掘频繁项集需要干什么。

首先需要从后向前遍历相似项链表的列表(这一列表已经在第一次扫描中按全局支持度排过序了)的每一项。

对每一项递归地进行如下步骤:

①记录前缀路径。我使用的方法是用一个HashSet记录前缀路径中出现的所有节点。

②记录该FP树的每一item的支持度。类似于前面的第一次扫描。

③根据记录的支持度,如果item频繁,则该item和当前的后缀为频繁项集。

④再根据record构建该FP树的相似项链表列表,去除掉非频繁项(类似第一次扫描)和当前item构成条件FP树。这里并不需要重新建立一个FP树的结构来构成条件FP树,因为记录前缀路径只需要访问相似项和父项。

⑤对相似项链表列表的剩余项再进行①步骤,直到相似项链表列表中没有项,为终止。

/**
     * 算法执行函数
     * @param minSupCnt 最小支持度计数
     * @param path 文件路径
     * @param pT 输出结果的项集大小阈值
     */
    public void run(int minSupCnt,String path,int pT) throws IOException {
        this.printThreshold = pT;
        this.minSupCnt = minSupCnt;
        scanDataSet(path);
        buildFPTree();
        for(int i = similarSingleItemLinkedListHeadList.size()-1;i>=0;i--){
            genFreqItemSet(similarSingleItemLinkedListHeadList.get(i).getItemValue()
                    ,fpTree,similarSingleItemLinkedListHeadList,new TreeSet<>());
        }
        //genFreqItemSet(14,fpTree,similarSingleItemLinkedListHeadList,new TreeSet<>());
        System.out.println("频繁项集个数:\t"+cntOfFreqSet);
    }
/**
     * 生成频繁项集
     * @param last 最后项
     * @param fPTree 条件FP树
     * @param fatherSimilarSingleItemLinkedListHeads 父树的相似项头结点链表
     * @param freqItemSet 频繁项集
     */
    private void genFreqItemSet(int last,FPTree fPTree,
                                List<SimilarSingleItemLinkedListHead>fatherSimilarSingleItemLinkedListHeads,TreeSet<Integer>freqItemSet) {

        FPTree conditionalFPTree = new FPTree();
        List<SimilarSingleItemLinkedListHead>similarSingleItemLinkedListHeads = new ArrayList<>();

        TreeSet<Integer>localFreqItemSet = (TreeSet<Integer>) freqItemSet.clone();
        int index ;
        index = searchForItemInHeadsList(last,
                (ArrayList<SimilarSingleItemLinkedListHead>) fatherSimilarSingleItemLinkedListHeads);

        Node firstNode = fatherSimilarSingleItemLinkedListHeads.get(index).next;
        HashSet<Node>record = new HashSet<>();  //用于记录前缀路径上出现的节点
        //记录前缀路径
        if(firstNode!=null){
            record.add(firstNode);
            Node nodeToVisitFather = firstNode;
            Node nodeToVisitSimilar = firstNode;
            while (nodeToVisitSimilar!=null){
                nodeToVisitSimilar.supInCFP = nodeToVisitSimilar.sup;
                nodeToVisitFather = nodeToVisitSimilar;
                while (nodeToVisitFather!=null){
                    // 计算supInCFT
                    if(nodeToVisitFather!=nodeToVisitSimilar)
                        nodeToVisitFather.supInCFP += nodeToVisitSimilar.supInCFP;
                    record.add(nodeToVisitFather);
                    nodeToVisitFather = nodeToVisitFather.father;
                }
                nodeToVisitSimilar = nodeToVisitSimilar.nextSimilar;
            }

            //记录在子树中的支持度
            Hashtable<Integer,Integer> supRecord = new Hashtable<>();
            record.forEach(new Consumer<Node>() {
                @Override
                public void accept(Node node) {
                    int item = node.item;
                    if(item == -1 ){    //根节点
                        return;
                    }
                    if(supRecord.containsKey(item)){
                        supRecord.put(item,supRecord.get(item)+ node.supInCFP);
                    }else{
                        supRecord.put(item,node.supInCFP);
                    }

                }
            });
            //输出结果
            if(supRecord.get(last)>=minSupCnt){
                localFreqItemSet.add(last);
                if(localFreqItemSet.size()>=printThreshold && !result.contains(localFreqItemSet)){
                    cntOfFreqSet++;
//                    for(int i = localFreqItemSet.size()-1;i>=0;i--){
//                        System.out.print(localFreqItemSet.get(i)+" ");
//                    }
                    localFreqItemSet.forEach(new Consumer<Integer>() {
                        @Override
                        public void accept(Integer integer) {
                            System.out.print(integer+" ");
                        }
                    });
                    result.add(localFreqItemSet);

                    System.out.println("");
                }
            }

            //构建相似项链表
            record.forEach(new Consumer<Node>() {
                @Override
                public void accept(Node node) {
                    if(node.item == -1){    //根节点
                        Node visitNode = node;
                        buildConditionalFPTree(conditionalFPTree.root, visitNode,record,
                                (ArrayList<SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeads,supRecord,last);
                    }
                }
            });
            //按支持度降序排序
            similarSingleItemLinkedListHeads.sort(new Comparator<SimilarSingleItemLinkedListHead>() {
                @Override
                public int compare(SimilarSingleItemLinkedListHead o1, SimilarSingleItemLinkedListHead o2) {
                    return o2.getSupTotal() - o1.getSupTotal();
                }
            });

            if(similarSingleItemLinkedListHeads.size()>=1){
                //递归搜索频繁项
                for(int i =similarSingleItemLinkedListHeads.size()-1;i>=0;i--){
                    genFreqItemSet(similarSingleItemLinkedListHeads.get(i).getItemValue(),
                            conditionalFPTree,similarSingleItemLinkedListHeads,localFreqItemSet);
                    // similarSingleItemLinkedListHeads.remove(i);
                }
            }
        }
    }
/**
     * 递归构建条件FP树
     * @param rootNode 以该节点为根向下建立条件FP树
     * @param originalNode  rootNode对应在原树中的节点
     * @param record    前缀路径
     * @param similarSingleItemLinkedListHeads  相似项表头链表
     * @param supRecord 支持度计数的记录
     * @param last 最后项
     */
    private void buildConditionalFPTree(Node rootNode,Node originalNode,HashSet<Node>record
            ,ArrayList<SimilarSingleItemLinkedListHead>similarSingleItemLinkedListHeads,Hashtable<Integer,Integer>supRecord,int last){
        if(originalNode.children!=null){
            for(int key:originalNode.children.keySet()){    //遍历originalNode的所有儿子节点,检查其是否在前缀路径中
                Node tempNode = originalNode.children.get(key);
                if(record.contains(tempNode)){
                    Node addedNode = new Node(tempNode.item, tempNode.supInCFP);
                    if(last == key){    //去除last的所有节点
                        tempNode.supInCFP = 0;
                        continue;
                    }
                    if(supRecord.get(key)>=minSupCnt){
                        //addedNode 拷贝 tempNode除儿子节点外的属性
                        addedNode.supInCFP = tempNode.supInCFP;
                        rootNode.children.put(tempNode.item, addedNode);
                        addedNode.father = rootNode;
                        //构建相似项表
                        int i = searchForItemInHeadsList(tempNode.item,similarSingleItemLinkedListHeads);
                        if(i==-1){
                            similarSingleItemLinkedListHeads.add(new SimilarSingleItemLinkedListHead(key,addedNode, addedNode.supInCFP));
                        }else{
                            similarSingleItemLinkedListHeads.get(i).setSupTotal(similarSingleItemLinkedListHeads.get(i).getSupTotal()+addedNode.supInCFP);
                            Node visitNode = similarSingleItemLinkedListHeads.get(i).next;
                             while (visitNode.nextSimilar!=null){
                                visitNode = visitNode.nextSimilar;
                            }
                            if(visitNode!=addedNode){
                                visitNode.nextSimilar= addedNode;
                            }
                        }
                        buildConditionalFPTree(addedNode,originalNode.children.get(key),record,similarSingleItemLinkedListHeads,supRecord,last);
                        addedNode.supInCFP = 0; //将supInCFP重置为0;
                    }else{
                        buildConditionalFPTree(rootNode,originalNode.children.get(key),record,similarSingleItemLinkedListHeads,supRecord,last);
                    }

                }
            }
        }
    }

完整代码

FP-Growth

到此这篇关于详解Java如何实现FP-Growth算法的文章就介绍到这了,更多相关Java实现FP-Growth算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 详解Java实现拓扑排序算法

    目录 一.介绍 二.拓扑排序算法分析 三.拓扑排序代码实现 一.介绍 百科上这么定义的: 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前.通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列.简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序. 为什么会有拓扑排序?拓

  • 如何用Java实现排列组合算法

    需求 我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些"奇妙"的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试. 抽象一下就是从一个集合中取出任意元素,形成唯一的组合.如[a,b,c]可组合为[a].[b].[c].[ab].[bc].[ac].[abc]. 要求如下: 组合内的元素数大于 0 小于等于 数组大小: 组合内不能有重复元素,如 [aab] 是不符合要求的组合: 组合内元素的位置随意,即 [ab] 和 [ba] 视为同一种组合:

  • 详解Java实现分治算法

    目录 一.前言 二.分治算法介绍 三.分治算法经典问题 3.1.二分搜索 3.2.快速排序 3.3.归并排序(逆序数) 3.4.最大子序列和 3.5.最近点对 四.结语 一.前言 在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱.但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了 当然如果你觉得各个部分

  • 贪心算法原理及在Java中的使用

    贪心算法 由于贪心算法本身的特殊性,我们在使用贪心算法之前必须要进行证明,保证算法满足贪心选择性质.具体的证明方法无外乎就是通过数学归纳法来进行证明.但大部分人可能并不喜欢枯燥的公式,因而我这里提供一个使用贪心算法的小技巧.由于贪心算法某种程度上算是动态规划算法的特例,使用条件比较苛刻,因而能够用动态规划解决的问题尽量都是用动态规划来进行先解决,如果在用完动态规划之后,提交时发现问题超时,并且进行状态压缩之后仍然超时,此时我们就可以**考虑使用贪心算法来进行解决.**最后强调一下,我们在使用贪心

  • 教你怎么用Java回溯算法解数独

    一.题干 输入一个9*9二维数组表示数独,已经填入的数字用1-9表示,待填入的数字用0表示,试写一个算法解出数独并输出. 二.思路 容易想到回溯法,即以人的思维的解数独,遍历数组,如果是空白就从1-9依次选一个数判断本行.列.3*3宫格内是否有重复,如果有就进行下一个数字的选择:如果该数暂时满足条件,那么进行下一个格子的选择,递归的终止条件是遍历完所有格子. 三.代码分段演示 输入数组 Scanner sc = new Scanner(System.in); int[][] board = ne

  • 总结一些Java常用的加密算法

    一.加密算法分类 加密算法通常分为三类: 对称加密 指加密和解密使用相同密钥的加密算法.对称加密算法的优点在于加解密效率高且易于实现. 不可逆加密 不可逆加密算法的特征是加密过程不需要密钥,并且经过加密的数据无法被解密,只有同样输入的输入数据经过同样的不可逆算法才能得到同样的加密数据. 非对称加密 指加密和解密使用不同密钥的加密算法,也称为公私钥加密. 二.加密算法的应用 1.数字签名:进行身份认证和数据完整性验证,主要用到了非对称密钥加密技术与数字摘要技术. 2.数字证书:主要用来确保数字签名

  • 详解Java Fibonacci Search斐波那契搜索算法代码实现

    一, 斐波那契搜索算法简述 斐波那契搜索(Fibonacci search) ,又称斐波那契查找,是区间中单峰函数的搜索技术. 斐波那契搜索采用分而治之的方法,其中我们按照斐波那契数列对元素进行不均等分割.此搜索需要对数组进行排序. 与二进制搜索不同,在二进制搜索中,我们将元素分成相等的两半以减小数组范围-在斐波那契搜索中,我们尝试使用加法或减法来获得较小的范围. 斐波那契数列的公式是: Fibo(N)=Fibo(N-1)+Fibo(N-2) 此系列的前两个数字是Fibo(0) = 0和Fibo

  • 详解Java实现的k-means聚类算法

    需求 对MySQL数据库中某个表的某个字段执行k-means算法,将处理后的数据写入新表中. 源码及驱动 kmeans_jb51.rar 源码 import java.sql.*; import java.util.*; /** * @author tianshl * @version 2018/1/13 上午11:13 */ public class Kmeans { // 源数据 private List<Integer> origins = new ArrayList<>()

  • 详解Java如何实现FP-Growth算法

    FP-Growth算法的Java实现 这篇文章重点讲一下实现.需要两次扫描来构建FP树 第一次扫描 第一次扫描,过滤掉所有不满足最小支持度的项:对于满足最小支持度的项,按照全局支持度降序排序. 按照这个需求,可能的难点为如何按照全局支持度对每个事务中的item排序. 我的实现思路 扫描原数据集将其保存在二维列表sourceData中 维护一个Table,使其保存每个item的全局支持度TotalSup 在Table中过滤掉低于阈值minSup的项 将Table转换为List,并使其按照Total

  • 详解Java分布式系统中一致性哈希算法

    业务场景 近年来B2C.O2O等商业概念的提出和移动端的发展,使得分布式系统流行了起来.分布式系统相对于单系统,解决了流量大.系统高可用和高容错等问题.功能强大也意味着实现起来需要更多技术的支持.例如系统访问层的负载均衡,缓存层的多实例主从复制备份,数据层的分库分表等. 我们以负载均衡为例,常见的负载均衡方法有很多,但是它们的优缺点也都很明显: 随机访问策略.系统随机访问,缺点:可能造成服务器负载压力不均衡,俗话讲就是撑的撑死,饿的饿死. 轮询策略.请求均匀分配,如果服务器有性能差异,则无法实现

  • 详解Java双轴快速排序算法

    目录 一.前言 二.回顾单轴快排 三.双轴快排分析 3.1.总体情况分析 3.2.k交换过程 3.3.收尾工作 四.双轴快排代码 一.前言 首选,双轴快排也是一种快排的优化方案,在JDK的Arrays.sort()中被主要使用.所以,掌握快排已经不能够满足我们的需求,我们还要学会双轴快排的原理和实现才行. 二.回顾单轴快排 单轴快排也就是我们常说的普通快速排序,对于快速排序我想大家应该都很熟悉:基于递归和分治的,时间复杂度最坏而O(n2),最好和平均情况为O(nlogn). 而快排的具体思路也很

  • 详解Java如何实现数值校验的算法

    给定一个字符串如何判断它是否为数值类型?例如:字符串+100.5e2.-123.3.1416以及-1E-16都表示数值,为数值类型,但12e.1a3.14.1.2.3.+-5以及12e+5.4都不是. 本文将带着大家实现这个判断算法,欢迎各位感兴趣的开发者阅读本文. 实现思路 我们先来看一下数值的定义规则:表示数值的字符串遵循模式A[.[B]][e|EC]或者.B[e|EC],其中: A为数值的整数部分 B紧跟着小数点为数值的小数部分 C紧跟着e或者E为数值的指数部分 在小数里可能没有数值的整数

  • 详解Java中KMP算法的图解与实现

    目录 图解 代码实现 图解 kmp算法跟之前讲的bm算法思想有一定的相似性.之前提到过,bm算法中有个好后缀的概念,而在kmp中有个好前缀的概念,什么是好前缀,我们先来看下面这个例子. 观察上面这个例子,已经匹配的abcde称为好前缀,a与之后的bcde都不匹配,所以没有必要再比一次,直接滑动到e之后即可. 那如果好前缀中有互相匹配的字符呢? 观察上面这个例子,这个时候如果我们直接滑到好前缀之后,则会过度滑动,错失匹配子串.那我们如何根据好前缀来进行合理滑动? 其实就是看当前的好前缀的前缀和后缀

  • 详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

    目录 简介 工作过程 总体思路 实现 小根堆 Dijsktra 测试 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边.对应问题:在无向图G=(V,E)中,假设每条边E(i)的长度W(i),求由顶点V0到各节点的最短路径. 工作过

随机推荐