Shortest path between all pairs with colored nodes

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.

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 20182 of these combinations, so it's still constant time.

So you can certainly do this in O(n2) 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(n2) time when all edges are known to be green-adjacent.

StackExchange Computer Science Q#119905, answer score: 2