3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So, I can't really see the difference between your solution and mine. Discarding all edges with no green vertex will just leave all paths that include ONLY 2 black vertices. in that case, our shortest path will be the single edge that connects them both. Other then that, our solution is equal? $\endgroup$ – goldi Jan 24 at 15:16
  • 1
    $\begingroup$ Each black vertex can connect to many (up to 2018) green ones, so there can be up to 2018^2 paths between a black pair. It's not a "single edge that connects them both" $\endgroup$ – Matt Timmermans Jan 24 at 17:03
-1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The whole purpose of the exercise is to drive home the point that constants are constant, even when they're big. $\endgroup$ – Matt Timmermans Jan 24 at 14:39
  • $\begingroup$ I specifically stated that the amount of green vertices is exactly 2018. In that case Floyed Warshall runs at O(2018^3) which is still a constant time. $\endgroup$ – goldi Jan 24 at 15:17
  • 1
    $\begingroup$ O(G^3) is O(1) if G is a constant. Big-O notation is useful for analyzing how the speed of an algorithm changes as its inputs grow. It does not "inherently mean this solution would take X computations at most". $\endgroup$ – BlueRaja - Danny Pflughoeft Jan 24 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.