Package algs44

Class BellmanFordSP

java.lang.Object

algs44.BellmanFordSP

public class BellmanFordSP
extends Object

Field Summary

Fields

Modifier and Type	Field	Description
private int	cost
private Iterable<DirectedEdge>	cycle
private final double[]	distTo
private final DirectedEdge[]	edgeTo
private final boolean[]	onQueue
private final Queue<Integer>	queue

Constructor Summary

Constructors

Constructor	Description
BellmanFordSP(EdgeWeightedDigraph G, int s)

Method Summary

Modifier and Type	Method	Description
private boolean	check(EdgeWeightedDigraph G, int s)
double	distTo(int v)
private void	findNegativeCycle()
boolean	hasNegativeCycle()
boolean	hasPathTo(int v)
static void	main(String[] args)
Iterable<DirectedEdge>	negativeCycle()
Iterable<DirectedEdge>	pathTo(int v)
private void	relax(EdgeWeightedDigraph G, int v)

Methods inherited from class java.lang.Object

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

Field Details

distTo

private final double[] distTo

edgeTo

private final DirectedEdge[] edgeTo

onQueue

private final boolean[] onQueue

queue

private final Queue<Integer> queue

cost

private int cost

cycle

private Iterable<DirectedEdge> cycle

Constructor Details

BellmanFordSP

public BellmanFordSP(EdgeWeightedDigraph G,
 int s)

Method Details

relax

private void relax(EdgeWeightedDigraph G,
 int v)

hasNegativeCycle

public boolean hasNegativeCycle()

negativeCycle

public Iterable<DirectedEdge> negativeCycle()

findNegativeCycle

private void findNegativeCycle()

hasPathTo

public boolean hasPathTo(int v)

distTo

public double distTo(int v)

pathTo

public Iterable<DirectedEdge> pathTo(int v)

check

private boolean check(EdgeWeightedDigraph G,
 int s)

main

public static void main(String[] args)