Problem 4 - Graph Algorithms

Considering an algorithm to find the shortest path between two vertices in an undirected graph with nonnegative edge length, answer the following questions:

1.

Let the numbers of vertices and edges in the graph be $n$ and $m$, respectively. Describe the shortest path algorithm whose running time is at most $O(n^2)$, and show its complexity.

2.

What is the appropriate data structure for the algorithm described above?

See [SED00] for a detailed answer.