首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    图论--差分约束系统

    求x1-x4的最大值,由题目给的式子1,2,4可得x1-x4>=11,我们来看图中最短路,x1到X4的最短距离也是11,也就是说差分约束系统就是将给定条件转化为图的过程,说白了还是建图,建完图,就看这个图的性质确定用什么最短路算法即可,是否有无解的情况,依照最短路算法什么时候无解呢?当有负环时无解,也就是说这里如果不确定是否无解的时候,可以用SPFA先判断一下,如果存在负环,就直接无解,只存在负的权值的话,就直接SPFA,优化什么花里胡哨的应改也用不到,全部为正权值的时候直接迪杰斯特拉完事,就这么简单,这个算法主要是考察的怎么将问题转化为差分约束,进而建图,这是这个问题的关键,因为求解只是一遍最短路的事。

    02

    最短路径四大算法「建议收藏」

    熟悉的最短路算法就几种:bellman-ford,dijkstra,spfa,floyd。 bellman-ford可以用于边权为负的图中,图里有负环也可以,如果有负环,算法会检测出负环。 时间复杂度O(VE); dijkstra只能用于边权都为正的图中。 时间复杂度O(n2); spfa是个bellman-ford的优化算法,本质是bellman-ford,所以适用性和bellman-ford一样。(用队列和邻接表优化)。 时间复杂度O(KE); floyd可以用于有负权的图中,即使有负环,算法也可以检测出来,可以求任意点的最短路径,有向图和无向图的最小环和最大环。 时间复杂度O(n3); 任何题目中都要注意的有四点事项:图是有向图还是无向图、是否有负权边,是否有重边,顶点到自身的可达性。 1、Dijkstra(单源点最短路) 这个算法只能计算单元最短路,而且不能计算负权值,这个算法是贪心的思想, dis数组用来储存起始点到其他点的最短路,但开始时却是存的起始点到其他点的初始路程。通过n-1遍的遍历找最短。每次在剩余节点中找dist数组中的值最小的,加入到s数组中,并且把剩余节点的dist数组更新。

    03

    PTA 数据结构与算法题目集(中文)7-7 六度空间 (30分) 题解

    “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。” “六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

    02
    领券