Which Shortest-Path Algorithm Should be Used?

Computer Science Level 1

Shortest-path algorithms are useful for certain types of graphs. For the graph below, which algorithm should be used to solve the single-source shortest path problem?

Graph Graph

Dijkstra Bellman-Ford Johnson Floyd-Warshall

View wiki
Alex Chumbley by Alex Chumbley , 28, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Alex Chumbley
May 24, 2016

Relevant wiki: Shortest Path Algorithms

This graph is a directed graph with negative edge weights. There are no negative weight cycles, so shortest paths will be well defined. However, since there are negative edge weights, Dijkstra's algorithm cannot be used.

Floyd-Warshall and Johnson's algorithm are for all-pairs shortest path algorithms.

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Abhi Deshmukh
Oct 10, 2017

As it is Single Source Shortest Path Floyd-Warshall & Johnson algorithm will be having very less priority to use. As the negative edge is given then surely Bellman-Ford Algo will be used

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...