graph – Dijkstra for The Single-Source Longest Path

by

No, we cannot1 – or at the very least, no polynomial reduction/modification is known – longest path problem is NP-Hard, while dijkstra runs in polynomial time!

If we can find a modfication to dijsktra to answer longest-path problem in polynomial time, we can derive P=NP

If not, then provide a counterexample.

This is very bad task. The counter example can provide a specific modification is wrong, while there could be a different modification that is OK.

The truth is we do not know if longest-path problem is solveable in polynomial time or not, but the general assumption is – it is not.

regarding just changing the relaxation step:

        A
       / \
      1   2
     /     \
    B<--1---C
edges are (A,B),(A,C),(C,B)

dijkstra from A will first pick B, and then B is never reachable – because it is out of the set of distances.

At the very least, one will have also to change min heap into max heap, but it will have a different counter-example why it fails.

(1) probably, maybe if P=NP it is possible, but it is very unlikely.

More Related Contents:

  1. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  2. How does Dijkstra’s Algorithm and A-Star compare?
  3. Find cycle of shortest length in a directed graph with positive weights
  4. Why does Dijkstra’s algorithm use decrease-key?
  5. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  6. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  7. Reverse the ordering of words in a string
  8. How to create the most compact mapping n → isprime(n) up to a limit N?
  9. Hash table runtime complexity (insert, search and delete)
  10. Find the shortest path in a graph which visits certain nodes
  11. How do you validate a binary search tree?
  12. design a stack such that getMinimum( ) should be O(1)
  13. Best algorithm to test if a linked list has a cycle
  14. Array remove duplicate elements
  15. Find connected components in a graph [closed]
  16. Finding all the shortest paths between two nodes in unweighted undirected graph
  17. What is the fastest way to find the closest point to a given point?
  18. Algorithm for “nice” grid line intervals on a graph
  19. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  20. insert, delete, max in O(1)
  21. In Order Successor in Binary Search Tree
  22. Algorithm for autocomplete?
  23. What is the advantage to using Bloom filters?
  24. Search a sorted 2D matrix [duplicate]
  25. Why are hash table expansions usually done by doubling the size?
  26. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  27. Algorithm for merging two max heaps?
  28. Why is vector array doubled?
  29. Finding connected components of adjacency matrix graph
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment