Goseeko blog

What is Single Source Shortest Path?

by Team Goseeko

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!

You may also like