CS6515 - Final exam - GA Final Exam Dyn. Prog, Div. + Conquer, Graphs, and NP-Completeness /complete solution

Traversing, reversing, copying, or otherwise working on the full graph running time - ANSWER-O(n+m) Checking, reading, or removing one vertex running time - ANSWER-O(1) Iterating, checking, reading, removing, or otherwise working on all vertices running time - ANSWER-O(n) Checking, reading, or removing one edge running time - ANSWER-O(m) Iterating, checking, or otherwise working on all edges running time - ANSWER-O(n+m) Explore Algorithm - ANSWER-Running time: O(n+m) Graphs: Any (not weight aware) Inputs: Graph and start vertex v Outputs: Visited array set to true for vertices reachable from v BFS Algorithm - ANSWER-Running time: O(n+m) Graphs: Any (not weight aware) Inputs: Graph and a start vertex Outputs: Distance array set to the shortest path between v and a reachable vertex u. INF if not reachable Dijkstra's Algorithm - ANSWER-Running time: O((n+m) log n) Graphs: Any weighted, no negative edge-weights allowed Inputs: Graph and a start vertex Outputs: Distance array with shortest weighted path from start vertex to all reachable vertexes Bellman-Ford Alg