org.dromara.hutool.core.map.multi

Class DirectedWeightGraph<T>

java.lang.Object

org.dromara.hutool.core.map.multi.DirectedWeightGraph<T>

Type Parameters:

T - 点对象类型

public class DirectedWeightGraph<T>
extends Object

权重有向图 基于 SPFA 算法实现 可以处理负边 可以进行负权环路检查

Author:

NewshiJ

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DirectedWeightGraph.Edge<T> 边
static class	DirectedWeightGraph.NegativeRingException 负环异常
static class	DirectedWeightGraph.Path<T> 路径

Constructor Summary

Constructors

Constructor and Description
DirectedWeightGraph()

Method Summary

Modifier and Type	Method and Description
Map<T,DirectedWeightGraph.Path<T>>	bestPathMap(T startPoint) 计算 从 startPoint 到 所有点 最短路径 基于 SPFA 算法实现
Set<T>	getAllPoints() 获取全部点
void	putEdge(T fromPoint, T nextPoint, long weight) 添加边
void	removeEdge(T fromPoint, T nextPoint) 删除边
void	removePoint(T point) 删除点
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

DirectedWeightGraph

public DirectedWeightGraph()

Method Detail

getAllPoints

public Set<T> getAllPoints()

获取全部点

Returns:

全部点

putEdge

public void putEdge(T fromPoint,
                    T nextPoint,
                    long weight)

添加边

Parameters:

fromPoint - 开始点

nextPoint - 结束点

weight - 权重

removeEdge

public void removeEdge(T fromPoint,
                       T nextPoint)

删除边

Parameters:

fromPoint - 开始点

nextPoint - 结束点

removePoint

public void removePoint(T point)

删除点

Parameters:

point - 点

toString

public String toString()

Overrides:

toString in class Object

bestPathMap

public Map<T,DirectedWeightGraph.Path<T>> bestPathMap(T startPoint)
                                               throws DirectedWeightGraph.NegativeRingException

计算 从 startPoint 到 所有点 最短路径 基于 SPFA 算法实现

Parameters:

startPoint - 开始节点

Returns:

最佳路径集合 如果无可触达顶点 返回空 map

Throws:

DirectedWeightGraph.NegativeRingException - 存在负权环路