-1

Dijkstra isn't assured to work on graphs with negative weights: Why doesn't Dijkstra's algorithm work for negative weight edges?, but can I assume it works for one of the following cases (even with negative weights)

  1. Directed Graph with no Directed Cycles

  2. Directed Graph which its infrastructure graph is a tree (Connected and have no Cycles)

Note: By infrastructure graph I mean the same graph while removing the directions of all edges.

  • This sounds like a homework problem, so you are probably only interested in dijkstra's algorithm. However, if this is a legitimate question outside of homework, you will probably be interested to know there is an algorithm that finds the longest path on a DAG based on topological sort. This should be of interest to you because the longest path on DAG is a near equivalent problem to 1. . – ldog Oct 12 '22 at 20:13

1 Answers1

3

For 1. there are many counterexamples which you can find by searching, and some are given in the Q&A you linked to.

For 2., if the undirected version of the graph is a tree, then there cannot be more than one path between any two nodes. So whatever path Dijkstra's algorithm finds will be the shortest by default. I'll leave it to you to show that Dijkstra's algorithm does find a path if one exists.

kaya3
  • 47,440
  • 4
  • 68
  • 97