$3.$ a$)$ Use a Greedy Algorithm that could be used to solve the "All$-$Pairs" Shortest Path

problem. Describe the algorithm step$-$by$-$step, including what data structures you would use to store your data.

Does this algorithm always work? Explain

What is the runtime of your algorithm? Explain

b$)$ Describe a Dynamic Algorithm step$-$by$-$step that could be used to solve the "All$-$Pairs" Shortest Path problem, including what data structures you would use to store your data. What is the difference between the greedy algorithm and the dynamic algorithm? What is the runtime of the dynamic approach? Explain Does it always work? Explain

$4.$ Given the attached DIRECTED GRAPH:

a$)$ Execute a Depth$-$First Search on the graph, with the following conditions:

NOTE:

Start from vertex B$.$ Follow the "normal DFS$"$ algorithm using DIRECTED edges! There are three types of edges on a DFS di$-$graph: Forward edges are edges u v with v not previously visited. Use a solid line Back edges are edges u v with v already visited. Use a dotted line. Cross edges are edges uv $($where there is no edge u$->$ v$).$ Use a dotted line.

b$)$ Are there any directed cycles in the given graph? Identify them by the vertices in order.

c$)$ Is this graph strongly connected? $($Is there a directed path between every pair of vertices?$)$