Let n denote the number of vertices and m denote the number of edges. We will assume that the shortest path between two vertices u, v V is unique, and denote it be (u, v). That is, (u, v) is the length of the path of (u, v).

1) Let G(V, E) be a graph with arbitrary weights on its edges, and let s V . Suggest an O(m) time algorithm that finds whether in a graph G(V, E) there is v V such that the shortest path s v contains more than 9 edges.