首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >加权有向图----无环情况下的最短路径算法

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

作者头像
SuperHeroes
发布2018-05-30 17:54:11
1.5K0
发布2018-05-30 17:54:11
举报
文章被收录于专栏:云霄雨霁云霄雨霁

上一篇:Dijkstra算法

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

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

该方法将顶点的放松与拓扑排序结合起来,首先将distTos初始化为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算法(可以处理含有负权边的图,但不能含有负权环)

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017.12.22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档