You are not logged in. Please login at www.codechef.com to post your questions!

×

BFS - properties

Hi there,
i'm trying to understand the bfs properties(last one) which is described here

can anyone explain . thanks in advance :)
Find the shortest path of even length from a source vertex s to a target vertex t in an unweighted graph: For this, we must construct an auxiliary graph, whose vertices are the state (v,c), where v - the current node, c=0 or c=1 - the current parity. Any edge (a,b) of the original graph in this new column will t<urn into two edges ((u,0),(v,1)) and ((u,1),(v,0)). After that we run a BFS to find the shortest path from the starting vertex (s,0) to the end vertex (t,0).

asked 15 Dec '18, 00:38

knakul853's gravatar image

3★knakul853
162
accept rate: 20%

edited 16 Dec '18, 10:08

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×494

question asked: 15 Dec '18, 00:38

question was seen: 77 times

last updated: 16 Dec '18, 10:08