美文网首页Daily Reading 群的分享
挑战程序设计竞赛11.7

挑战程序设计竞赛11.7

作者: 程序员一飞 | 来源:发表于2016-11-07 21:27 被阅读71次

今天读的挑战程序设计竞赛的图的最短路问题,只看了一个dijkstra算法,但没怎么看明白。

又把昨天的bellman-ford算法看了一遍,比昨天理解的又透彻一些。

这两个算法都是单源最短路,就是固定一个起点,然后求这个点到其他所有点的最短距离的意思。

由于固定一个起点,首先应该想到的是先计算靠近它的点,然后往远处求。

所以根据这个思路写出一个递推式:记从起点s到顶点i的最短距离为d[i],

  d[i]=min{d[j]+ (顶点j到i的权值)|e=(j,i)∈E }

相关文章

  • 挑战程序设计竞赛11.7

    今天读的挑战程序设计竞赛的图的最短路问题,只看了一个dijkstra算法,但没怎么看明白。 又把昨天的bellma...

  • 用快速幂运算求斐波那契,时间复杂度降到O(logn)

    思路来自《挑战程序设计竞赛》 可运行的C++代码如下

  • 简介

    这是关于《挑战程序设计竞赛(第2版)》的刷题记录。因为POJ评测快,全英文,评测结果反馈与ICPC竞赛相同,所以选...

  • 挑战程序设计竞赛11.4

    /* 今天读了一种叫做并查集的数据结构,以前做题做到了,但一些解题报告质量参差不齐, 自己只是理解个大概了,不知道...

  • 挑战程序设计竞赛11.2

    今天读了如何实现优先队列,及如何运用。可以用数组来表示二叉树,节点是从上到下从左到右的顺序紧凑排列,它最重要的性质...

  • 挑战程序设计竞赛11.3

    今天读了二叉搜索树的实现以及set和map的简单用法。 二叉搜索树实际上就是一颗二叉树,但它有一个特点,就是每个节...

  • 挑战程序设计竞赛11.11

    今天在高铁上读了一点,只看了辗转相除法。 int gcd(int a,int b){ if(b==0) retur...

  • 挑战程序设计竞赛11.5

    今天读了挑战程序设计竞赛的2.5,介绍了图的一些概念。 图的表示方法,邻接矩阵和邻接表。 邻接矩阵可以简单地建一个...

  • 多重集组合数

    在挑战程序设计竞赛第69页公式dp[i+1][j] = dp[i][j] + dp[i+1][j-1] - dp[...

  • 2015年“甲骨文杯”“全国Java程序设计大赛”

    一、竞赛介绍 “全国Java程序设计大赛”是面向全国各大高等院校在校学生和社会技术人士的程序设计竞赛活动。通过竞赛...

网友评论

    本文标题:挑战程序设计竞赛11.7

    本文链接:https://www.haomeiwen.com/subject/cooouttx.html