NichkeCoder's blog

By NichkeCoder, history, 6 weeks ago, In English,

Hi, this is my first time writing here. I've recently gotten into algorithms (2.5-3 months ago) and I've started learning Floyd Warshall a few days ago. One problem I've found on CP Algorithms (regarding this topic) is Traveling Graph (21D) here on CF. I've done the FW for the shortest path and found a way to tell if there is no solution at all, but that's as far as I've gotten. I've been challenging myself for four days but after some research today I found out it is similar to Traveling Salesman problem — is this the write way to approach the problem or is there a way to do it using Floyd's algo, if so could you elaborate on it further? Thanks.

Problem Link: https://codeforces.com/problemset/problem/21/D

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a well-known problem in graph theory called the Chinese Postman Problem (CPP). Check the following article for more information.

Arc Routing Problem, Part I: The Chinese Postman Problem

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you very much, I think I am starting to get the algo now. :) It took me a while to get the difference between TS and TPP, so just to clarify the difference between Traveling Salesman and Chinese Postman is that in the first one we need to travel all the vertices and in the second one all the edges. Right? Thanks once again.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. Add to this clarification that in the Chinese Postman Problem each edge should be visited at least once.