aud.example.graph.DijkstraShortestPaths Class Reference

implements Dijkstra's algorithm by defining priority More...

Inheritance diagram for aud.example.graph.DijkstraShortestPaths:

Collaboration diagram for aud.example.graph.DijkstraShortestPaths:

Public Member Functions
	DijkstraShortestPaths (MyGraph g)
String	name ()
	get traversal name More...
Public Member Functions inherited from aud.example.graph.PriorityFirstSearch
	PriorityFirstSearch (MyGraph g)
void	start (MyNode s0)
	start traversal at node s0 More...
Public Member Functions inherited from aud.example.graph.Traversal
	Traversal (MyGraph g)
	initiate traversal of g More...
abstract String	name ()
	get traversal name More...
abstract void	start (MyNode s0)
	start traversal at node s0 More...
void	showMark (MyNode node)
	callback to give visual feedback on marking a node More...

Protected Member Functions
double	priority (MyNode node, MyEdge e)
	Compute priority of a node: More...
abstract double	priority (MyNode node, MyEdge e)
	Compute priority of a node: More...
Protected Member Functions inherited from aud.example.graph.Traversal
void	initialize ()
	initialize graph for traversal (reset all attributes), provided for convenience to be called by start More...

Additional Inherited Members
Public Attributes inherited from aud.example.graph.Traversal
SingleStepper	singlestepper = null
	may halt if single stepper was set More...
int	nsteps = 1
	halt every nsteps steps in time_ More...
int	verbose = 0
	set verbosity (extra output if >0) More...
Protected Attributes inherited from aud.example.graph.PriorityFirstSearch
Comparator< MyNode >	compareNodes
	comparator for {#link aud.PriorityQueue} More...
Protected Attributes inherited from aud.example.graph.Traversal
MyGraph	g_ = null
int	time_ = 0

Detailed Description

implements Dijkstra's algorithm by defining priority

Definition at line 4 of file DijkstraShortestPaths.java.

Constructor & Destructor Documentation

DijkstraShortestPaths()

aud.example.graph.DijkstraShortestPaths.DijkstraShortestPaths

(

MyGraph

g

)

Definition at line 6 of file DijkstraShortestPaths.java.

                                          {
    super(g);
  }

Member Function Documentation

name()

String aud.example.graph.DijkstraShortestPaths.name

(

)

get traversal name

Reimplemented from aud.example.graph.Traversal.

Definition at line 15 of file DijkstraShortestPaths.java.

{ return "PFS (Dijkstra)"; }

priority()

double aud.example.graph.DijkstraShortestPaths.priority ( MyNode  node, MyEdge  e  )

protected

Compute priority of a node:

• node.d+e.getWeight() for Dijkstra's algorithm to find shortest paths (and the shortest path tree)
• e.getWeight() for Prim's algorithm to find the minimum spanning tree

Reimplemented from aud.example.graph.PriorityFirstSearch.

Definition at line 10 of file DijkstraShortestPaths.java.

                                                            {
    assert(!Double.isInfinite(node.d));
    return node.d+(e.hasWeight() ? e.getWeight() : 1.0);
  }

References aud.example.graph.MyNode.d, aud.graph.SimpleEdge.getWeight(), and aud.graph.AbstractEdge.hasWeight().

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• DijkstraShortestPaths.java