专栏首页云霄雨霁加权有向图----无环情况下的最短路径算法

加权有向图----无环情况下的最短路径算法

上一篇:Dijkstra算法

如果加权有向图不含有向环,则下面要实现的算法比Dijkstra算法更快更简单。它有以下特点:

  • 能够在线性时间内解决单点最短路径问题
  • 能够处理负权重的边
  • 能够解决相关的问题,例如找出最长的路径

该方法将顶点的放松与拓扑排序结合起来,首先将distTo[s]初始化为0,其他distTo[]初始化为无穷大,然后一个个地按照拓扑排序放松所有顶点。

按照拓扑排序放松顶点,就能在和V+E成正比的时间内解决无环加权有向图的单点最短路径问题。

public class AcyclicSP {
	private DirectedEdge[] edgeTo;
	private double[] distTo;
	
	public AcyclicSP(EdgeWeightedDigraph G,int s) {
        //初始化
		edgeTo = new DirectedEdge[G.V()];
		distTo = new double[G.V()];
		for(int v = 0;v<G.V();v++)
			distTo[v] = Double.POSITIVE_INFINITY;
		distTo[s] = 0.0;
		//拓扑排序对象
		Tolpological top = new Tolpological(G);
        //按照拓扑排序放松顶点
		for(int v: top.order())    
			relax(G,v);
	}
    //relax()、distTo()、hasPathTo()、pathTo()同Dijkstra算法
}

改实现中不需要marked[]数组,因为按照拓扑排序处理不可能再次遇到已经被放松过的顶点。

下一篇:Bellman-Ford算法(可以处理含有负权边的图,但不能含有负权环)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法总结

    SuperHeroes
  • 设计模式----命令模式

    SuperHeroes
  • 字符串排序----低位优先的字符串排序

    SuperHeroes
  • 基于 Knative 打造生产级 Serverless 平台 | KubeCon NA2019

    董一韬 蚂蚁金服产品经理,致力于驱动云计算相关产品,包括云原生 PaaS 平台、容器与 Serverless 产品等,与最终顾客紧密合作,帮助客户在规模化的金融...

    CNCF
  • 数据分析学习之不得不知的八大算法详解

    学习数据分析的朋友们都知道,算法是不可或缺的,或者说算法在一定程度上可以更好的量化的一个人的学习能力和水平。本文整理了经典的八大算法,相关的资料希望能帮助大家了...

    加米谷大数据
  • Python数据结构与算法笔记(5)

    邻接矩阵优点是简单,对于小图,很容易看到哪些节点连接到其他节点。但是大多数单元格是空的,即稀疏。

  • 深入浅出Kubernetes架构!!建议收藏

    Kubernetes 已经成为容器编排领域的王者,它是基于容器的集群编排引擎,具备扩展集群、滚动升级回滚、弹性伸缩、自动治愈、服务发现等多种特性能力。

    架构师修行之路
  • 我花了10个小时,写出了这篇K8S架构解析!

    互联网技术飞速发展的今天,为了承载请求的高并发和业务的多样性,微服务的架构成了各个公司的标配。

    macrozheng
  • 我花了10个小时,写出了这篇K8S架构解析

    互联网技术飞速发展的今天,为了承载请求的高并发和业务的多样性,微服务的架构成了各个公司的标配。

    马哥linux运维
  • 快速排序算法思路分析和C++源代码(递归和非递归)

      快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试...

    waylon

扫码关注云+社区

领取腾讯云代金券