I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly. The question is:
Let's say we have a directed graph with no cycles, it has
N vertices and
Exactly 2018 vertices are colored green, and the others are black.
We know that in each shortest
path, each vertex is colored green,
perhaps without the first and the last node.
We can find the shortest path of all two pairs of nodes in:
O(___) and not less
What I tried:
If we run the
Floyd Warshall algorithm on the 2018 green vertices we get the shortest path between all pairs of greens. (This is
O(1) because of the green vertices amount is constant).
Now for each (u,v) in
- If both u and v are green we already have the shortest path from
- If one is green and the other black, we add the edge's weight that connects the source/destination to the green group and add the
- If both u and v, are black, we add the lightest weight of each which connects to the green group.
I think my solution is kind of messy, and I do not know if it's 100% correct.
The solution is: We can find the shortest path of all two pairs of nodes in:
O(n^2) and not less.