Shortest path between all pairs with colored nodes

Question

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 M edges. 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 VxV:

• If both u and v are green we already have the shortest path from Floyd Warshall.
• 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 Floyd Warshall result.
• 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.

Answer 1

Your answer and reasoning are correct, but the last steps in your algorithm are wrong.

First, discard all edges with no green vertex. Then:

To find the shortest path between a green and black node, you have to consider all of the black node's green-adjacent edges, and add the shortest path to/from the green. There are at most 2018 of these, so it's still constant time.

To find the shortest path between two black nodes, you have to consider all combinations of their green-adjacent edges, and add the distance between the greens. There are at most 2018² of these combinations, so it's still constant time.

So you can certainly do this in O(n²) time, and you can't do any better, because that's also the size of the output.

It may be simpler just to show how you can optimize Floyd-Warshall to take O(n²) time when all edges are known to be green-adjacent.

Answer 2

The time complexity of Floyd Warshall to find shortest path among all pairs of nodes isn't O(n^2). It's O(n^3).

This is O(1) because of the green vertices amount is constant.

This is not correct. if the number of green node is G, then the complexity of running Floyd Warshall to find all pair shortest path among G nodes is - O(G^3).

Now the second part's complexity is correct. That's O(n^2) because you are traversing VxV nodes.

So your proposed solution would have a time complexity of - O(n^2 + G^3).

Now here what I don't know is - is N way more bigger than G(2018)? What you need to consider here - which one would take more computation? if n^2 is way bigger than G^3, then we can ignore the G^3 part as Big-O notation is the upper bound indication. And if G^3 is bigger then we can ignore the n^2 part.

Note - Now I am not sure about the not less part in your question. Big-O notation is the upper bound indication. This inherently mean that this solution would take X computation at most. You can see Big-O means not more. I think what your question expects is to find the lower bound(not less). If so, then it should have been Omega notation not Big-O.