+ 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
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".