美文网首页
最短路模型

最短路模型

作者: kisslight | 来源:发表于2017-03-28 15:37 被阅读0次

什么问题是最短路问题

对路径的合理选取使得这条路径上的权重最后的结果符合题目要求的问题,一般都能够通过最短路算法解决,在这样的一个大前提上,对于权值和路径的要求不同,可以使得问题发生不同的变种,根据是实际情况,采取不同的方法予以解决

对于特定问题的特定分析

对于最短路问题的变形大致有以下的几种可能

  • 求解路径中是否存在负环类问题
  • 有向图中的往返最短问题
  • APSP问题
  • 最单纯的最短路问题
  • 最短路中的最长路问题
  1. 求解路径中是否存在负环类问题,对于一个问题,因为他们的权值使得出现一个能够对于在环上的点的路径的距离不断改变是这一类题目的特征,也就是说,无论是汇率,时间,只要是通过求解所存在的路上出现了对于某几个点的距离一直处于刷新状态,永远无法确定下来,就可以确定是一个求负环问题。
    对于求负环问题一般来说使用的是SPFA算法,对于负环问题,SPFA算法原理中本来就容许有负环存在,当一条路径的变换距离的操作已经超过了算法的容许度,按照定义,就可以知道其这样一条路中出现了负环回路。

  2. 有向图中的往返最短问题,这样的问题主要是有一个单源起点,然后题目一般通过各种方式询问它到某一个点的到和回来的问题,因为他是有向图,实际上也就解决了你到一个点而且回来的最短距离且边不重复使用的问题,这样的问题其实可以直接按照题意输入一次有向图,然后把原有向图的方向倒转,重新输入一次,这样子的话,实际上就是把回来的路变换方向变成再一次出去的路,重新转化成SPSP问题,这样的话根据图的稠密程度就可以使用dijkstra或者SPFA算法求解

  3. APSP问题,由于现在所接触到的最短路算法只有少数的几个,所以不是很清楚是否还有更优的解法,实际上现在观念中的对于APSP问题来说似乎是floyd算法比较有利,因为经过预处理之后就已经对所有的点的距离获得一个求解,所以查询的时候只会消耗O(1)的时间复杂度。但是近来似乎接触到了一种优化版的SPFA,在求解APSP问题的时候比floyd算法在比较短的时间内能够结局,因为对于floyd算法,所有最短路的距离是必须全部求解的,但是对于一些比较水一点的数据,其实它的查询是不一定能够达到APSP问题,所以我认为其实无论是在实际应用还是比赛中改良版的SPFA似乎都应该有更好的效率

  4. 最单纯的最短路问题的解决只需要注意到的是图是否是稠密图,然后针对其使用最短路算法就可以了,另外要插一句嘴,其实所谓的并行最短路问题也是最单纯的最短路问题(想一想为啥)

  5. 最短路的最长路问题,这个我只用过floyd和dijkstra算法解决,但是比较通用的算法应该是dijkstra算法,在经过最小heap优化之后,dijkstra算法对于更多的最短路存在一个适配性,虽然个人比较习惯的是SPFA就是了。对于贪心的过程进行一个中转量的使用就可以获得这个问题的解。

这个星期主要是重新理通了一遍所熟识的最短路算法的求解和原理,题目的难度实在是不高,可能是因为kuangbin并没找到这个专题的更难得变种,切起来比较简单,比较需要注意的是,因为一些私人的事情所以冲劲减少,不是很应该。对于算法的改良和证明讲解暂时不做说明,主要是因为比较繁琐。SPFA算法需要考虑和魔改的地方我也发到群里面去了。

在树上看到对于最短路问题似乎是有差分约束的拓展,这两天我找个时间了解一下,希望诸君效率也有一个提升,多少对得住自己便是了
鲫鱼
2017-3-28

相关文章

  • 最短路模型

    什么问题是最短路问题 对路径的合理选取使得这条路径上的权重最后的结果符合题目要求的问题,一般都能够通过最短路算法解...

  • NLP | ZCQ | 7.2 汉语分词方法

    重点:基于统计模型 7.2.1 N-最短路径方法 两个阶段 1. 用切分算法对句子词语进行初步切分,得到一个相对最...

  • Hanlp中使用纯JAVA实现CRF分词

    Hanlp中使用纯JAVA实现CRF分词 与基于隐马尔可夫模型的最短路径分词、N-最短路径分词相比,基于条件随机场...

  • 电力四种短路

    电力短路大如天,一旦发生破命钱 单相短路概率高,心中时刻设防线 三相短路最严重,预防发生常挂念 两相短路常发生,偶...

  • Floyd-Warshshall(未简化&数组版)

    解决多元最短路径问题(每两点之间的最短路):一次最外层循环表示借助一条边 初始化:d[i][i] = 0; 其他为...

  • 设计中的短路电流的校核

    短路电电流 一)为什么计算最大短路电流?为什么计算最小短路电流? 目的:测试对于短路计算意义的理解 答案:计算最大...

  • 遍历 最短路径 1.单源最短路 有权图-Dijkstra 多源头最短路-Floyd算法 —————————————...

  • BJT小信号模型电源视为短路(转载)

    原问题地址 内阻很小的电压源,接近理想电压源。一个理想的电压源,不管供出多大电流或充入多大电流,电源电压始终不变化...

  • 最短路径 之 Dijkstra 算法

    • 最短路径 之 Floyd 算法• 最短路径 之 Bellman 算法 Dijkstra算法是用于求解单源最短路...

  • 次短路算法

    次短路(一)从(父节点)到(子节点)次短路直接更新(通常在最短路已经确定的情况下才进行直接更新次短路)从(父节点)...

网友评论

      本文标题:最短路模型

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