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!