25. Below are four graph-based computational tasks. For each one, specify the type of graph most appropriate for the data in question in terms of undirected or directed, and unweighted or weighted. In addition, choose the graph algorithm from the following list best suited to computing a solution: Breadth-First Search, Minimum Spanning Tree (e.g. Prim's or Kruskal's), Dijkstra's Algorithm, Topological Sort, Depth-First Search. No additional explanation is required.

(a) You have data for the rail transport (i.e. train track) network in North America, including the length of each section of track. You need to compute the shortest (in terms of distance) route for a train traveling from New York City to Atlanta, GA.

(b) You need to lay water lines for a new housing development (i.e. pipes to carry water to and from each house). You have data on all the places it's possible to build pipes, and how much pipe would be required in each case. From the many potential pipeline options, you must compute which pipes to actually build such that you use the least amount of pipe overall.

(c) You are compiling a program from source code and you know the dependencies between source files (i.e. for each file F, you know which other files, if any, can't be compiled until F is compiled). You need to compute a valid compilation order such that each file is compiled after all of its dependencies are compiled.

(d) You have data about friend relationships from a social network, and you want to model the spread of a rumor based on these relationships. Your model is that a rumor starts with a single person, who then tells all of their friends. Then at each subsequent step, everyone who knows about the rumor spreads it to all of their friends who don't know it. You want to compute how many people know about the rumor after k steps.