+ 1

¿How can I learn about graph theory, on Competitive programing?

Hi. I wish learn about graph theory, dijsktra, floyd marshall, etc. I have competitive programming 3 but I don't understend it! :c

31st Mar 2021, 1:48 AM
MICAEL MIRANDA
MICAEL MIRANDA - avatar
1 Réponse
+ 3
Practice makes perfect. Practice with them will put your understanding to the test and reinforce it for you. I would write some code with automated tests. Since Dijkstra's algorithm and Floyd Warshall both find shortest paths between nodes, you could automatically test for a few hand made test cases. You could also randomly generate a bunch of graphs and compare results from each algorithm. If any cases get different results, there's a bug. If you want additional practice, you could implement similar programs in the different languages you might compete with. You tagged the question with python, c++ and c. You could implement those algorithms in each of those. Graph theory is a pretty broad subject but Dijkstra and Floyd-Warshall are specific enough and writing the above program will require a good understanding of at least 1 way to represent a graph and some manipulation of them. If you don't already have a programming contest list to practice with, check https://www.hackerrank.com/ They have a bunch of problem solving questions and some are classified under "graph theory".
31st Mar 2021, 2:01 AM
Josh Greig
Josh Greig - avatar