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

142 private double totalWeight; // Total weight of all edges in the tree total weight in tree

143
144 public MST( int root, int [] parent, List<Integer> searchOrder,

145 double totalWeight) {

146 super (root, parent, searchOrder);

147 this .totalWeight = totalWeight;

148 }
149
150 public double getTotalWeight() {

151 return totalWeight;

152 }
153 }
154
155 /** Find single source shortest paths */
156 public ShortestPathTree getShortestPath( int sourceVertex) {
157 // cost[v] stores the cost of the path from v to the source
158 double [] cost = newdouble [getSize()];
159 for ( int i = 0 ; i < cost.length; i++) {
160 cost[i] = Double.POSITIVE_INFINITY; // Initial cost set to infinity
161 }
162 cost[sourceVertex] = 0 ; // Cost of source is 0
163
164 // parent[v] stores the previous vertex of v in the path
165 int [] parent = newint [getSize()];
166 parent[sourceVertex] = -1 ; // The parent of source is set to -1
167
168

getShortestPath

initialize cost

// T stores the vertices whose path found so far

169 List<Integer> T = new ArrayList<>();

shortest path tree

170
171 // Expand T

172 while (T.size() < getSize()) { expand tree

173 // Find smallest cost v in V - T

174 int u = -1 ; // Vertex to be determined

175 double currentMinCost = Double.POSITIVE_INFINITY;

176 for ( int i = 0 ; i < getSize(); i++) {

177 if (!T.contains(i) && cost[i] < currentMinCost) {

178 currentMinCost = cost[i];

179 u = i;

vertex with smallest cost

180 }
181 }
182
183 T.add(u); // Add a new vertex to T add to T

184
185 // Adjust cost[v] for v that is adjacent to u and v in V - T
186 for (Edge e : neighbors.get(u)) {
187 if (!T.contains(e.v)
188 && cost[e.v] > cost[u] + ((WeightedEdge)e).weight) {
189

cost[e.v] = cost[u] + ((WeightedEdge)e).weight;

adjust cost
adjust parent

190 parent[e.v] = u;

191 }
192 }
193 } // End of while
194
195

// Create a ShortestPathTree

196 return new ShortestPathTree(sourceVertex, parent, T, cost);

create a tree

197 }
198
199

/** ShortestPathTree is an inner class in WeightedGraph */

200 public class ShortestPathTree extends Tree {

shortest path tree
cost

201 private double [] cost; // cost[v] is the cost from v to source