Relocatable hierarchical software design
Friday, April 11, 2014
Implementation analysis of Dijkstra's algorithm - shortest path to single source
Algorithmic Analysis and object oriented design of Dijkstra's algorithm
- shortest path to single source
start
Data model datatypes, public api used:
Graph<N, W>
Collection<Node<N, W>> getNodeList()
Node<N, W>
Collection<Edge<N, W>> getAdjList()
Edge<N, W>
W getWeight()
Node<N, W> getTarget()
ShortestD<N, W>
void initMax()
void setWeight(Node<N, W> t, W w)
W getWeight(Node<N, W> node)
Prev<N, W>
void setPrevious(Node<N, W> t, Node<N, W> s)
SPQueue<N, W> //Fib/bin heap impl
Node<N, W> removeMin()
void addDecrease(Node<N, W> t, W w)
Processing data public api
ShortestD<N, W> getDistance()
SPQueue<N, W> getQueue()
Prev<N, W> getPrev()
Node<N, W> getSource()
Graph<N, W> getGraph()
initialize:
distance[graph nodes] to
∞
previous[graph nodes] to
none
distance[source node] to
0
add source node to queue
while queue is not empty
exit
loop
distance[v] is shortest distance
previous[v] specifies shortest path
remove minimum distance node u from queue
for each adjacent edge e of u do
exit
loop
v is target node of e
v new distance := distance[u] + e weight
if (v new distance < distance[v]) set:
distance[v] := v new distance
previous[v] := u
add/update v, v new distance in Q
draw flowcharts logically from specification
Use the specification to generate objects
No comments:
Post a Comment
Newer Post
Older Post
Home
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment