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.me/problemset/problem/21/D
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
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.
Yes. Add to this clarification that in the Chinese Postman Problem each edge should be visited at least once.