无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

  • 解决思路:动态规划

1、首先使用邻接矩阵存储无向图

2、将找到结点1到节点N的最短路径分解成结点1到节点i的最短路径(1<i<节点数)

3、对于每一个未计算的结点i,考虑已经计算过的当前最短路径端点choice,如果结点i和结点j直接有边,则计算从结点choice到未计算结点的最短路径

d[i]=min{A[i][j]+A[j]}

源码

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.lang.Integer;
import java.util.Set;

public class NoPointerChart {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();   //输入点数
        int E = in.nextInt();   //输入边数

        int[][] A = new int[V][V];

        for (int i = 0; i < V; i++) {   //初始化所有边为无穷大
            for (int j = 0; j < V; j++) {
                A[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < E; i++) {   //输入每一条边
            int j = in.nextInt();
            int k = in.nextInt();
            int v = in.nextInt();
            A[j - 1][k - 1] = v;
            A[k - 1][j - 1] = v;
        }

        Set<Integer> unVisited = new HashSet<>(V);  //记录未访问节点
        Set<Integer> visitied = new HashSet<>(V); //记录已经访问的节点
        int[] d = new int[V];
        for (int i = 1; i < V; i++) {   //初始化最优解都为无限大
            unVisited.add(i);
            d[i] = Integer.MAX_VALUE;
        }
        visitied.add(0);
        d[0] = 0;

        int choice = 0;  //中间节点下标,每次选出当前结点到所有可达未标记结点的最短路径端点
        while (unVisited.size() > 0) {   //当仍然有未标记结点的时候 
            int tempMin = Integer.MAX_VALUE;  //记录从中间节点到所有可达结点中的最小值(最短路径)
            int tempMinI = -1;  //记录最短路径的端点下标
            Iterator<Integer> iti = unVisited.iterator();
            while (iti.hasNext()) {  //对于所有未标记的结点
                int i = iti.next();
                if (A[choice][i] != Integer.MAX_VALUE) {   //如果中间结点到此未标记结点有边
                    if(d[i]>A[choice][i] + d[choice])   //计算中间结点到当前结点的最短路径
                        d[i] = A[choice][i] + d[choice];
                    if (d[i] < tempMin) {   //计算当前结点到所有可达未标记结点的最短路径
                        tempMin = d[i]; 
                        tempMinI = i;
                    }

                }
            }
            unVisited.remove(tempMinI);visitied.add(tempMinI);  //将当前结点记录未已经标记
            choice = tempMinI; //重新定位中间结点
        }

        System.out.println(d[V-1]);
    }
//测试用例 第一行输入结点数V和边数E ,以下E行输入每条边的端点和权值
//6 9
//1 2 6
//1 3 3
//2 3 2
//2 4 5
//3 4 3
//3 5 4
//4 5 2
//4 6 3
//5 6 5
}

参考 http://www.hawstein.com/posts/dp-novice-to-advanced.html 参考 http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

21060
来自专栏王硕

原 B树C语言代码实现

750100
来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

34810
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

547100
来自专栏nnngu

数据结构08 线索二叉树

上一篇总结了二叉树,这一篇要总结的是线索二叉树,我想从以下几个方面进行总结。 1、什么是线索二叉树? 2、为什么要建立线索二叉树? 3、如何将二叉树线索化? 4...

35760
来自专栏猿人谷

单链表

线性表的链式表示和实现       线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以使不连续的)。因此,为...

32350
来自专栏desperate633

LintCode 带重复元素的子集题目代码

9830
来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

27390
来自专栏用户画像

4.5.3 哈弗曼树(Huffman)树和哈弗曼编码

树中结点被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的...

8310
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

20970

扫码关注云+社区

领取腾讯云代金券