Instead of decorating an edge with just a weight (a double), Felice needs a weight (a double representing distance), a route number (an int), and a name (a String). What changes have to be made to the interface to support this? What changes need to be made to the internal representation of vertices and edges?

What will be an ideal response?

The situation here is similar to that described in the last question and the answer is similar. Another possibility is to add a new type specifier to the definition of WeightedGraph, something like:
public interface WeightedGraph extends Graph

and change the methods accordingly. For example,

W getEdgeWeight( Vertex v1, Vertex v2 );