The Internet vs. The Shortest and Longest Path Problems

Whilst revising algorithms and complexity theory, I came across the longest path problem again and read it was NP-hard. Then I thought to myself, isn’t this just equivalent to finding the shortest path in the graph with the edge weights negated? I decided to use Google to confirm my intuition (looking back I should have tried to prove it to myself beforehand). My search was simply of the form: can the longest path problem be solved with a shortest path algorithm, e.g. is it possible to use Dijkstra’s to find the longest path in the graph? I came across many sources claiming you cannot “because longest path is NP-hard”. I was a bit confused, went through the examples some websites provided and still I thought to myself, isn’t this still just equivalent to the shortest path on -G? Well, it is. It’s pretty obvious if you think about it but many sources say otherwise. In fact upon further reading of Wikipedia, they claim it to be so; although under their “Acyclic graphs and critical paths” section.

Continue Reading...

New Blog, New World

This will be my new blogging area. I’ve moved away from my WordPress blog and moved to my website, which is hosted by GitHub pages using Jekyll. Soon I’ll be deleting my old WordPress blog. So watch out world!

Continue Reading...