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