Shortest path algorithm

general
1

Can Someone provide easy implementation using c++ STL of:

1)Bellman Ford’s Algorithm:

2)Dijkstra’s Algorithm

3)Floyd–Warshall’s Algorithm

I will be very thankful. Thank YOu.

2

all are available on geeks for geeks
check it …
first try to implement by urself whether right or not
u will learn and remember it for long

1 Like
3

It will be a bit big, as i will explain everything. Here is a link to very simple and straight Dijkstra’s algorithm problem and the

solution

Please read a bit of theory of Dijkstra on internet or via some book, hope you’ll find it easily.

Code explanation goes as:

**To do>>> You are supposed to find shortest path form vertex 1 to the last one, i.e. number of vertexes equals last one as they are contiguously numbered from 1 to n (n=number of vertices)

1)Have a path array, fill it from 1 to till n with infinity (very high value) (isolating them, as per algo, representing none connected to none.

2)Because i will be doing a backtracking to find path, so have an array called parent, will store parent of each node (to know where we came down from), initially parent of root/start node i.e. startV will be ‘-1’, and will use it to stop iteration(later explained)–(simply saying start node has no parent, rest we will calculate)

3)Then calls Dijkstra(), followed by print_path() function.

Dijkstra Explanation goes as:

1)shortest path queue is a priority queue that will hold weight and then to what node this weight is nodes name (actually number) in a pair respective to order as , in descending order of weight, generally highest is given priority, but it will hold the minimum at top using greater() in priority queue defination (pq=priority queue), google rests of the pq syntax

2)Dijkstra function has a one time initialization of pq, holding 0 weight/distance to startV, (not considering self loop cases)

------- As per algorithm, we calculate adjacent nodes distances of all waiting nodes and traverse the minimum among them all, the pq will hold them all and will have min. at top, so we won’t need to find min among them all, this will speed up search and reduce complexities (please note: we don’t traverse currents nodes adjacent min, rather among all waiting nodes adj.'s)

------- We will return 0 from find shortest path function in case if all nodes have been traversed, and we are done or we have nothing to traverse to currV i.e. current vertex, so in case if we have reached either endV (desired) vertex or have nothing to traverse , we will return. i.e. if currV==endV or currV=0, then return

3)call function find_shortest(), to find shortest among waiting nodes. As till now pq has only node 1, i.e. starting node with distance 0, (pq holds waiting/temporary nodes whose min distance hasn’t been finalized yet), the function returns the top of pq, and pop out the top, this makes next waiting node as shortest.

4)once we have shortest i.e. start node in first iteration, as its a greedy selection, there must be no way shorter than this, so we set its path status as true, i.e. a shortest path is found (please google for verification of greedy approach), and then traverse its all adjacent nodes (i.e. that have edge connecting to it, push them all to pq, this way pq will have the minimum at top, and we will keep on finalizing the distance of one node in each iteration, there’s no shorter way, we need to traverse them all)

  1. if path of currV i.e. 1, which is parent plus (+) for each its adj’s i.e. child is smaller than path till found that particular child, we will update it child path along with its parent as ‘currV’ which is 1 for first iteration and push it to pq , i.e. waiting list, (we initialized path with infinity, isolated, we we have a smaller path for first iteration)

6)set its path, push it to pq, and update its parent

7)Keep doing this and updating and finalizing the path of top of pq in each iteration.

8)if the pq is empty, this means there is no edge connecting us with end node (any more node), or we are node iterating all nodes and theres no point repeatedly visiting nodes that has final distances set to true.

  1. or in case if currV==endV is the desired edge that we want. we return. Now every edge must be having a parent. if we reached endV i.e. our desired V , it must also have a parent, else 0, as being global, will hold 0 as defalut value.

we will call printpath and if endV has parent as 0, we are done (no path possible), else we will print endV then its parent and so on till we reach -1 as parent of startV

i haven’t calculated the shortest path distance/weight, only has traced the shortest path, try calculating the path weighte and printing it, you can do it both way , backward or forward or while looping, try doing that or other variations.

if you are looking for a simple Dijkstra algo. without priority queue (pq) at top of solution i have provided link to my failing code one test case 31, time limit exceeded TLE, as that took too long, feel free to check that.
Now you know the STL functions, try implementing the rest ones yourself, if fails, geeksforgeeks has solution to them.

1 Like
4

I want Soln for it . An easy one. Please anyone provide me with it. pls

Pls help @vijju123 or @meooow or anyone else

5

nice expanation !

1 Like
6

@coderslegacy

http://theoryofprogramming.com/bellman-ford-algorithm-using-cpp-stl/

here are some easy solutions !!

7

i mentioned it above !!
here are some more links …

this codeforces has everything …