title: Shortest path in a complement graph algorithm
body: <p>I had a test today (Data Structures course), and one of the questions was the following:
  Given an undirected, non-weighted graph G=(V,E), you need to write an algorithm that for a given node s, returns the shortest path from s to all the nodes v' in the complement graph.</p>
  
  <p>A Complement Graph G'=(E',V') contains an edge between any to nodes in G that don't share an edge, and only those.</p>
  
  <p>The algorithm needs to run in O(V+E) (of the original graph).</p>
  
  <p>I asked 50 different students, and not even one of them solved it correctly.</p>
  
  <p>any Ideas?
  Thanks a lot,
  Barak.</p>