**Features of Single Source Shortest Path**

- Single Source Shortest Path is Weighted graph directed.
- Edges may have adverse costs.
- No loop whose price is < 0.0.
- Find the shortest path to each of the n vertices of the digraph from a given source vertex.
- Where there are negative-cost edges, Dijkstra’s O(n2) single-source greedy algorithm does not work.
- The Bellman-Ford algorithm finds the bottom-up gap. It first finds certain distances in the route that have only one edge. Increase the length of the route after that to find all possible solutions.

## Single Source **Shortest Path Problem**

Given a non-negative linked directed graph G with a non-negative graph Edge weights and root vertex r, find a directed path P(x) from r to x for each vertex x, such that the sum of the edge weights in path P(x) is as small as possible.

In 1959, by the Dutch computer scientist Edsger Dijkstra.

Solves a graph with non-negative edge weights for the single-source shortest path problem.

In routing, this algorithm is also used.

E.g.: The algorithm of Dijkstra is generally the working theory behind the link-state. Protocols of Routing

**Bellman-ford Algorithm**

- All-destinations of single-source shortest paths in
- Digraphs with cost-negative edges.
- Dynamic programming is used.
- Runs when adjacency matrices are used in O(n3) time.
- Runs in O(ne) time while using adjacency lists.

**Algorithm**

bellmanFord(dist, pred, source)

Input − Distance list, predecessor list and the source vertex.

Output** **− True, when a negative cycle is found.

Begin

iCount := 1

maxEdge := n * (n – 1) / 2 //n is the number of vertices

for all vertices v of the graph, do

dist[v] := ∞

pred[v] := ϕ

done

dist[source] := 0

eCount := number of edges present in the graph

create edge list named edgeList

while iCount < n, do

for i := 0 to eCount, do

if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i)

dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i)

pred[edgeList[i].v] := edgeList[i].u

done

done

iCount := iCount + 1

for all vertices i in the graph, do

if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i), then

return true

done

return false

End

Interested in learning about similar topics? Here are a few hand-picked blogs for you!