WEIGHTED GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1095

F IGURE 29.28

The program can add vertices and edges and display MST dynamically.

edge, and the distance between the two vertices is also displayed. (5) The user
drags a vertex while pressing the CTRL key to move a vertex. (6) The verti-
ces are numbers starting from 0 . When a vertex is removed, the vertices are
renumbered. (7) You can click the Show MST or Show All SP From the Source
button to display an MST or SP tree from a starting vertex. (8) You can click
the Show Shortest Path button to display the shortest path between the two
specified vertices.

***29.18

( Alternative version of Dijkstra algorithm ) An alternative version of the Dijk-
stra algorithm can be described as follows:

Input: a weighted graph G = (V, E) with non-negative weights
Output: A shortest path tree from a source vertex s

1 ShortestPathTree getShortestPath(s) {
2 Let T be a set that contains the vertices whose
3 paths to s are known;
4 Initially T contains source vertex s with cost[s] = 0 ;
5 for (each u in V - T)
6 cost[u] = infinity;
7
8 while (size of T < n) {
9 Find v in V - T with the smallest cost[u] + w(u, v) value
10 among all u in T;
11 Add v to T and set cost[v] = cost[u] + w(u, v);
12 parent[v] = u;
13 }
14 }

add initial vertex

more vertex
find next vertex

add a vertex

The algorithm uses cost[v] to store the cost of a shortest path from vertex v
to the source vertex s . cost[s] is 0 . Initially assign infinity to cost[v] to
indicate that no path is found from v to s . Let V denote all vertices in the graph
and T denote the set of the vertices whose costs are known. Initially, the source
vertex s is in T . The algorithm repeatedly finds a vertex u in T and a vertex v
in V - T such that cost[u] + w(u, v) is the smallest, and moves v to T .
The shortest path algorithm given in the text coninously update the cost and
parent for a vertex in V - T . This algorithm initializes the cost to infinity for
each vertex and then changes the cost for a vertex only once when the vertex is
added into T . Implement this algorithm and use Listing 29.7, TestShortestPath.
java, to test your new algorithm.