Timeline for Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 30, 2017 at 11:04 | comment | added | xavierm02 | @TienanhNguyen No. If you get the shortest path using $w'$, you may not get a shortest path for $w$ because of the length problem. And if you always keep track of the length and then use $w'(p)-|p|W$ whenever you compare, then you're just using $w$ which can have negative edges so Dijkstra may not work. | |
| Mar 29, 2017 at 18:11 | comment | added | Tienanh Nguyen | But does the algorithm I mentioned above correct? Since Johnson a lot more complicated, I highly doubted that the algorithm above can do the same things as Johnson with less complexity. | |
| Mar 29, 2017 at 15:38 | history | edited | xavierm02 | CC BY-SA 3.0 |
deleted 111 characters in body
|
| Mar 29, 2017 at 15:31 | history | edited | xavierm02 | CC BY-SA 3.0 |
deleted 111 characters in body
|
| Mar 29, 2017 at 15:25 | history | edited | xavierm02 | CC BY-SA 3.0 |
added 264 characters in body
|
| Mar 29, 2017 at 15:20 | history | answered | xavierm02 | CC BY-SA 3.0 |