Chapter 29, Problem 29.11PE

Program Plan Intro

Find shortest paths

Program Plan:

• Create a package “main”.
  • Add a java class named “Edge” to the package which is used to get the edges from the graph.
  • Add a java class named “Graph” to the package which is used to add and remove vertices, edges.
  • Add a java class named “UnweightedGraph” to the package which is used to store vertices and neighbors.
  • Add a java class named “WeightedGraph” to the package which is used to get the weighted edges and print the edges.
  • Add a java class named “WeightedEdge” to the package which is used to compare edges.
  • Add a java class named “Test” to the package.
    • Import the required packages.
    • Declare the main class.
      • Give the “main ()” method.
        • Get the URL from the user.
        • Open the URL and read the string.
        • Get the number of vertices and store it in the variable “num”.
        • Print the number of vertices.
        • Create an array list.
        • Loop until End of file using “while” condition.
          • Read the line.
          • Split the string.
          • Loop through the length of the triplet.
            • Create an array and add the tokens.
            • Trim the edges and add the edges to the array list.
        • Create an object for the “WeightedGraph”.
        • Print the edges by calling the function “printWeightedEdges ()”.
        • Call the function “getShortestPath ()”.
        • Print the total weight of the minimum spanning tree.
        • Call the function “printPath ()”.