Question

What is the run time complexity of the given function and what does it do? You can assume minindex function takes O(n) and returns index of the minimum value of the given vector (20) vector alg(vector> graph, int source) { int s = graph.size(); vector cost; vector known; vector path; for(int i =0; i(cost[current] + graph[current] [i])) cost[i] = cost[current] + graph[current][i]; path[i] = current; } } return cost; }

Answer 1

The given function implements Dijkstra's shortest path algorithm, which finds the shortest path from a source node to all other nodes in a weighted graph. The run time complexity of the function is O(V^2), where V is the number of vertices in the graph. This is because the algorithm involves visiting each vertex once, and for each vertex, updating the cost (which involves a call to minindex function that takes O(n)) of all its neighboring vertices. Therefore, the overall time complexity is O(V * (V + n)). However, with the use of a priority queue to store the minimum cost vertices, the time complexity can be improved to O((V+E)logV), where E is the number of edges in the graph.