Unlike Dijkstras where we need to find the minimum value of all vertices, in Bellman-Ford, edges are considered one by one. | /Filter /FlateDecode A Graph Without Negative Cycle Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table. For instance, if there are different ways to reach from one chemical A to another chemical B, each method will have sub-reactions involving both heat dissipation and absorption. O ( V Then, the part of the path from source to u is a shortest path from source to u with at most i-1 edges, since if it were not, then there must be some strictly shorter path from source to u with at most i-1 edges, and we could then append the edge uv to this path to obtain a path with at most i edges that is strictly shorter than Pa contradiction. In such a case, the BellmanFord algorithm can detect and report the negative cycle.[1][4]. This procedure must be repeated V-1 times, where V is the number of vertices in total. graph->edge = (struct Edges*) malloc( graph->Edge * sizeof( struct Edges ) ); //Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges, // This function prints the last solution. Every Vertex's path distance must be maintained. Imagine a scenario where you need to get to a baseball game from your house. As a result, there will be fewer iterations. The pseudo-code for the Bellman-Ford algorithm is quite short. Let's say I think the distance to the baseball stadium is 20 miles. Will this algorithm work. Ltd. All rights reserved. E If the graph contains a negative-weight cycle, report it. V However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the BellmanFord algorithm simply relaxes all the edges, and does this Claim: After interation \(i\), for all \(v\) in \(V\), \(v.d\) is at most the weight of every path from \(s\) to \(v\) using at most \(i\) edges. On the \((i - 1)^\text{th} \) iteration, we've found the shortest path from \(s\) to \(v\) using at most \(i - 1\) edges. 1 We can find all pair shortest path only if the graph is free from the negative weight cycle. v.distance:= u.distance + uv.weight. Like Dijkstra's algorithm, BellmanFord proceeds by relaxation, in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. Dijkstra's Algorithm. V *Lifetime access to high-quality, self-paced e-learning content. | This step calculates shortest distances. The standard Bellman-Ford algorithm reports the shortest path only if there are no negative weight cycles. We can store that in an array of size v, where v is the number of vertices. times, where The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges. The second lemma guarantees that v. d = ( s, v) after rounds, where is the length of a minimum weight path from s to v. Share Cite Improve this answer Follow She's a Computer Science and Engineering graduate. If we want to find the set of reactions where minimum energy is required, then we will need to be able to factor in the heat absorption as negative weights and heat dissipation as positive weights. Learn how and when to remove this template message, "An algorithm for finding shortest routes from all source nodes to a given destination in general networks", "On the history of combinatorial optimization (till 1960)", https://en.wikipedia.org/w/index.php?title=BellmanFord_algorithm&oldid=1141987421, Short description is different from Wikidata, Articles needing additional references from December 2021, All articles needing additional references, Articles needing additional references from March 2019, Creative Commons Attribution-ShareAlike License 3.0. The graph is a collection of edges that connect different vertices in the graph, just like roads. Choose path value 0 for the source vertex and infinity for all other vertices. Please leave them in the comments section at the bottom of this page if you do. Subsequent relaxation will only decrease \(v.d\), so this will always remain true. Privacy Policy & Terms Of Condition & Affliate DisclosureCopyright ATechDaily 2020-23, Rename all files in directory with random prefix, Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example, Setting Up Unity for Installing Application on Android Device, Steps For Installing Git on Ubuntu 18.04 LTS. That is one cycle of relaxation, and it's done over and over until the shortest paths are found. BellmanFord algorithm can easily detect any negative cycles in the graph. A-143, 9th Floor, Sovereign Corporate Tower, We use cookies to ensure you have the best browsing experience on our website. times to ensure the shortest path has been found for all nodes. There are a few short steps to proving Bellman-Ford. A negative cycle in a weighted graph is a cycle whose total weight is negative. Dynamic Programming is used in the Bellman-Ford algorithm. So, after the \(i^\text{th}\) iteration, \(u.distance\) is at most the distance from \(s\) to \(u\). Explore this globally recognized Bootcamp program. Another way to improve it is to ignore any vertex V with a distance value that has not changed since the last relaxation in subsequent iterations, reducing the number of edges that need to be relaxed and increasing the number of edges with correct values after each iteration. With this early termination condition, the main loop may in some cases use many fewer than |V|1 iterations, even though the worst case of the algorithm remains unchanged. {\displaystyle |V|/3} Detect a negative cycle in a Graph | (Bellman Ford), Ford-Fulkerson Algorithm for Maximum Flow Problem, Prim's Algorithm (Simple Implementation for Adjacency Matrix Representation), Kruskal's Algorithm (Simple Implementation for Adjacency Matrix), QuickSelect (A Simple Iterative Implementation). The Bellman-Ford algorithm is able to identify cycles of negative length in a graph. If dist[u] + weight < dist[v], then | Usage. Try Programiz PRO: Consider this graph, it has a negative weight cycle in it. For the base case of induction, consider i=0 and the moment before for loop is executed for the first time. The algorithm can be implemented as follows in C++, Java, and Python: The time complexity of the BellmanFord algorithm is O(V E), where V and E are the total number of vertices and edges in the graph, respectively. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated paths. Choosing a bad ordering for relaxations leads to exponential relaxations. Therefore, after i iterations, v.distance is at most the length of P, i.e., the length of the shortest path from source to v that uses at most i edges. Relaxation 2nd time If there is a negative weight cycle, then shortest distances are not calculated, negative weight cycle is reported.1) This step initializes distances from source to all vertices as infinite and distance to source itself as 0. Edge contains two endpoints. In this way, as the number of vertices with correct distance values grows, the number whose outgoing edges that need to be relaxed in each iteration shrinks, leading to a constant-factor savings in time for dense graphs. The BellmanFord algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. For calculating shortest paths in routing algorithms. Relaxation works by continuously shortening the calculated distance between vertices comparing that distance with other known distances. Can we use Dijkstras algorithm for shortest paths for graphs with negative weights one idea can be, to calculate the minimum weight value, add a positive value (equal to the absolute value of minimum weight value) to all weights and run the Dijkstras algorithm for the modified graph. stream One example is the routing Information protocol. Not only do you need to know the length of the shortest path, but you also need to be able to find it. 1. Either it is a positive cost (like a toll) or a negative cost (like a friend who will give you money). This means that starting from a single vertex, we compute best distance to all other vertices in a weighted graph. Which sorting algorithm makes minimum number of memory writes? There will not be any repetition of edges. Find the obituary of Ernest Floyd Bellman (1944 - 2021) from Phoenix, AZ. Pseudocode of the Bellman-Ford Algorithm Every Vertex's path distance must be maintained. Negative weight edges can generate negative weight cycles, which reduce the total path distance by returning to the same point. PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc. In contrast, Bellman-ford simply // relaxes ALL of the edges V-1 times. The second row shows distances when edges (B, E), (D, B), (B, D) and (A, B) are processed. Input: Graph and a source vertex src Output: Shortest distance to all vertices from src. For this, we map each vertex to the vertex that last updated its path length. is the number of vertices in the graph. With a randomly permuted vertex ordering, the expected number of iterations needed in the main loop is at most Dijkstra doesnt work for Graphs with negative weights, Bellman-Ford works for such graphs. x]_1q+Z8r9)9rN"U`0khht]oG_~krkWV2[T/z8t%~^v^H [jvC@$_E/ob_iNnb-vemj{K!9sgmX$o_b)fW]@CfHy}\yI_510]icJ!/(+Fdg3W>pI]`v]uO+&9A8Y]d ;}\~}6wp-4OP /!WE~&\0-FLi |vI_D [`vU0 a|R~zasld9 3]pDYr\qcegW~jW^~Z}7;`~]7NT{qv,KPCWm] For this, we map each vertex to the vertex that last updated its path length. Bellman-Ford will only report a negative cycle if \(v.distance \gt u.distance + weight(u, v)\), so there cannot be any false reporting of a negative weight cycle. It first calculates the shortest distances which have at most one edge in the path. {\displaystyle |V|-1} Speci cally, here is pseudocode for the algorithm. Algorithm Pseudocode. The Bellman-Ford algorithm works by grossly underestimating the length of the path from the starting vertex to all other vertices. {\displaystyle |V|-1} For the Internet specifically, there are many protocols that use Bellman-Ford. If a vertex v has a distance value that has not changed since the last time the edges out of v were relaxed, then there is no need to relax the edges out of v a second time. Getting Started With Web Application Development in the Cloud, The Path to a Full Stack Web Developer Career, The Perfect Guide for All You Need to Learn About MEAN Stack, The Ultimate Guide To Understand The Differences Between Stack And Queue, Combating the Global Talent Shortage Through Skill Development Programs, Bellman-Ford Algorithm: Pseudocode, Time Complexity and Examples, To learn about the automation of web applications, Post Graduate Program In Full Stack Web Development, Advanced Certificate Program in Data Science, Cloud Architect Certification Training Course, DevOps Engineer Certification Training Course, ITIL 4 Foundation Certification Training Course, AWS Solutions Architect Certification Training Course. }OnMk|g?7KY?8 << An arc lies on such a cycle if the shortest distances calculated by the algorithm satisfy the condition where is the weight of the arc . And because it can't actually be smaller than the shortest path from \(s\) to \(u\), it is exactly equal. We also want to be able to get the shortest path, not only know the length of the shortest path. Conversely, suppose no improvement can be made. Let all edges are processed in following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). . So, the if statement in the relax function would look like this for the edge \((S, A):\), \[ \text{if }A.distance > S.distance + weight(S, A), \]. No votes so far! But BellmanFordalgorithm checks for negative edge cycles. But time complexity of Bellman-Ford is O(V * E), which is more than Dijkstra. Step 2: "V - 1" is used to calculate the number of iterations. dist[v] = dist[u] + weight We can see that in the first iteration itself, we relaxed many edges. Step 2: Let all edges are processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). Bellman-Ford algorithm, pseudo code and c code Raw BellmanFunction.c This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. It begins with a starting vertex and calculates the distances between other vertices that a single edge can reach. We are sorry that this post was not useful for you! You also learned C programming language code and the output for calculating the distance from the source vertex in a weighted graph. V Negative weights are found in various applications of graphs. Firstly we will create a modified graph G' in which we will add the base vertex to the original graph G. We will apply the Bellman-Ford ALgorithm to check whether the graph G' contains the negative weight cycle or not. Relaxation is safe to do because it obeys the "triangle inequality." Let's go over some pseudocode for both algorithms. We get the following distances when all edges are processed second time (The last row shows final values). The distance to each node is the total distance from the starting node to this specific node. The fourth row shows when (D, C), (B, C) and (E, D) are processed. This algorithm can be used on both weighted and unweighted graphs. Consider this weighted graph, Enter your email address to subscribe to new posts. Create an array dist[] of size V (number of vertices) which store the distance of that vertex from the source. After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated. This is done by relaxing all the edges in the graph for n-1 times, where n is the number of vertices in the graph. We stick out on purpose - through design, creative partnerships, and colo 17 days ago . 3 This edge has a weight of 5. Because of this, Bellman-Ford can also detect negative cycles which is a useful feature. 5. 1 Things you need to know. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. Bellman-Ford algorithm is a single-source shortest path algorithm, so when you have negative edge weight then it can detect negative cycles in a graph. You studied and comprehended the Bellman-Ford algorithm step-by-step, using the example as a guide. 1 6 0 obj Following are the applications of the bellman ford algorithm: Last but not least, you will need to perform practical demonstrations of the Bellman-Ford algorithm in the C programming language. The subroutines are not explained because those algorithms already in the Bellman-Ford page and the Dijkstra page.To help you relate the pseudo-code back to the description of the algorithm, each of the three steps are labeled. For any edge in the graph, if dist[u] + weight < dist[v], Negative weight cycle is present. Initialize dist[0] to 0 and rest values to +Inf. The algorithm then iteratively relaxes those estimates by discovering new ways that are shorter than the previously overestimated paths. Relaxation occurs |V| - 1 time for every |E| the number of edges, so you multiply the two and get the average, which is the quadratic time complexity of O. V Let u be the last vertex before v on this path. Shortest path algorithms like Dijkstra's Algorithm that aren't able to detect such a cycle can give an incorrect result because they can go through a negative weight cycle and reduce the path length. It is slower than Dijkstra's algorithm for the same problem but more versatile because it can handle graphs with some edge weights that are negative numbers. You can arrange your time based on your own schedule and time zone. While Dijkstra looks only to the immediate neighbors of a vertex, Bellman goes through each edge in every iteration. Initialize all distances as infinite, except the distance to the source itself. We need to maintain the path distance of every vertex. The first for loop sets the distance to each vertex in the graph to infinity. The Bellman-Ford algorithm uses the bottom-up approach. / Phoenix, AZ. ( Cormen et al., 2nd ed., Problem 24-1, pp. So, each shortest path has \(|V^{*}|\) vertices and \(|V^{*} - 1|\) edges (depending on which vertex we are calculating the distance for). We notice that edges have stopped changing on the 4th iteration itself. The correctness of the algorithm can be shown by induction: Proof. \(O\big(|V| \cdot |E|\big)\)\(\hspace{12mm}\). On your way there, you want to maximize the number and absolute value of the negatively weighted edges you take. | For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges. When you come across a negative cycle in the graph, you can have a worst-case scenario. There is another algorithm that does the same thing, which is Dijkstra's algorithm. Read our, // Recursive function to print the path of a given vertex from source vertex, // Function to run the BellmanFord algorithm from a given source, // distance[] and parent[] stores the shortest path (least cost/path), // information. Following that, in this Bellman-Ford algorithm tutorial, you will look at some use cases of the Bellman-Ford algorithm. In this step, we check for that. Bellman Ford's algorithm and Dijkstra's algorithm are very similar in structure. >> Space Complexity: O(V)This implementation is suggested by PrateekGupta10, Edge Relaxation Property for Dijkstras Algorithm and Bellman Ford's Algorithm, Minimum Cost Maximum Flow from a Graph using Bellman Ford Algorithm. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path. 67K views 1 year ago Design and Analysis of algorithms (DAA) Bellman Ford Algorithm: The Bellman-Ford algorithm emulates the shortest paths from a single source vertex to all other vertices. acknowledge that you have read and understood our, Data Structure & Algorithm Classes (Live), Data Structure & Algorithm-Self Paced(C++/JAVA), Android App Development with Kotlin(Live), Full Stack Development with React & Node JS(Live), GATE CS Original Papers and Official Keys, ISRO CS Original Papers and Official Keys, ISRO CS Syllabus for Scientist/Engineer Exam, Introduction to Graphs Data Structure and Algorithm Tutorials, Applications, Advantages and Disadvantages of Graph, Detect Cycle in a directed graph using colors, Detect a negative cycle in a Graph | (Bellman Ford), Cycles of length n in an undirected and connected graph, Detecting negative cycle using Floyd Warshall, Dijkstras Shortest Path Algorithm | Greedy Algo-7, Johnsons algorithm for All-pairs shortest paths, Karps minimum mean (or average) weight cycle algorithm, 0-1 BFS (Shortest Path in a Binary Weight Graph), Find minimum weight cycle in an undirected graph, Kruskals Minimum Spanning Tree Algorithm | Greedy Algo-2, Difference between Prims and Kruskals algorithm for MST, Applications of Minimum Spanning Tree Problem, Total number of Spanning Trees in a Graph, Reverse Delete Algorithm for Minimum Spanning Tree, All Topological Sorts of a Directed Acyclic Graph, Maximum edges that can be added to DAG so that it remains DAG, Topological Sort of a graph using departure time of vertex, Articulation Points (or Cut Vertices) in a Graph, Eulerian path and circuit for undirected graph, Fleurys Algorithm for printing Eulerian Path or Circuit, Count all possible walks from a source to a destination with exactly k edges, Word Ladder (Length of shortest chain to reach a target word), Find if an array of strings can be chained to form a circle | Set 1, Tarjans Algorithm to find Strongly Connected Components, Paths to travel each nodes using each edge (Seven Bridges of Knigsberg), Dynamic Connectivity | Set 1 (Incremental), Ford-Fulkerson Algorithm for Maximum Flow Problem, Find maximum number of edge disjoint paths between two vertices, Introduction and implementation of Kargers algorithm for Minimum Cut, Find size of the largest region in Boolean Matrix, Graph Coloring | Set 1 (Introduction and Applications), Traveling Salesman Problem (TSP) Implementation, Introduction and Approximate Solution for Vertex Cover Problem, Erdos Renyl Model (for generating Random Graphs), Chinese Postman or Route Inspection | Set 1 (introduction), Hierholzers Algorithm for directed graph, Boggle (Find all possible words in a board of characters) | Set 1, HopcroftKarp Algorithm for Maximum Matching | Set 1 (Introduction), Construct a graph from given degrees of all vertices, Determine whether a universal sink exists in a directed graph, Two Clique Problem (Check if Graph can be divided in two Cliques), Dijkstra's Shortest Path Algorithm | Greedy Algo-7. A distributed variant of the BellmanFord algorithm is used in distance-vector routing protocols, for example the Routing Information Protocol (RIP). 2 The algorithm processes all edges 2 more times. By using our site, you | This is noted in the comment in the pseudocode. Bellman ford algorithm is a single-source shortest path algorithm. 1.1 What's really going on here? Then, for the source vertex, source.distance = 0, which is correct. If there is a negative weight cycle, then shortest distances are not calculated, negative weight cycle is reported. 1 In a chemical reaction, calculate the smallest possible heat gain/loss. MIT. That can be stored in a V-dimensional array, where V is the number of vertices. | The second iteration guarantees to give all shortest paths which are at most 2 edges long. {\displaystyle O(|V|\cdot |E|)} This process is done |V| - 1 times. Negative weight edges can create negative weight cycles i.e. | Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 18 Prof. Erik Demaine. To review, open the file in an editor that reveals hidden Unicode characters. The second row shows distances when edges (B, E), (D, B), (B, D) and (A, B) are processed. | This pseudo-code is written as a high-level description of the algorithm, not an implementation. However, the worst-case complexity of SPFA is the same as that of Bellman-Ford, so for . Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. It is similar to Dijkstra's algorithm but it can work with graphs in which edges can have negative weights. This condition can be verified for all the arcs of the graph in time . Moving ahead with this tutorial on the Bellman-Ford algorithm, you will now learn the pseudocode for this algorithm. | Bellman-Ford algorithm. Claim: If the input graph does not have any negative weight cycles, then Bellman-Ford will accurately give the distance to every vertex \(v\) in the graph from the source. The following improvements all maintain the Complexity theory, randomized algorithms, graphs, and more. However, since it terminates upon finding a negative cycle, the BellmanFord algorithm can be used for applications in which this is the target to be sought for example in cycle-cancelling techniques in network flow analysis.[1]. This is simple if an adjacency list represents the graph. A.distance is set to 5, and the predecessor of A is set to S, the source vertex. The first row shows initial distances. The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path between a given source vertex and all other vertices in the graph. Introduction Needs of people by use the technology gradually increasing so that it is reasonably necessary to the acknowledge that you have read and understood our, Data Structure & Algorithm Classes (Live), Data Structure & Algorithm-Self Paced(C++/JAVA), Android App Development with Kotlin(Live), Full Stack Development with React & Node JS(Live), GATE CS Original Papers and Official Keys, ISRO CS Original Papers and Official Keys, ISRO CS Syllabus for Scientist/Engineer Exam, Bellman Ford Algorithm (Simple Implementation), Check if a graph is strongly connected | Set 1 (Kosaraju using DFS), Tarjans Algorithm to find Strongly Connected Components, Articulation Points (or Cut Vertices) in a Graph, Eulerian path and circuit for undirected graph, Fleurys Algorithm for printing Eulerian Path or Circuit, Hierholzers Algorithm for directed graph, Find if an array of strings can be chained to form a circle | Set 1, Find if an array of strings can be chained to form a circle | Set 2, Kruskals Minimum Spanning Tree Algorithm | Greedy Algo-2, Prims Algorithm for Minimum Spanning Tree (MST), Prims MST for Adjacency List Representation | Greedy Algo-6, Dijkstras Shortest Path Algorithm | Greedy Algo-7, Dijkstras Algorithm for Adjacency List Representation | Greedy Algo-8, Dijkstras shortest path algorithm using set in STL, Dijkstras Shortest Path Algorithm using priority_queue of STL, Dijkstras shortest path algorithm in Java using PriorityQueue, Java Program for Dijkstras shortest path algorithm | Greedy Algo-7, Java Program for Dijkstras Algorithm with Path Printing, Printing Paths in Dijkstras Shortest Path Algorithm, Tree Traversals (Inorder, Preorder and Postorder). Assume you're looking for a more in-depth study that goes beyond Mobile and Software Development and covers today's most in-demand programming languages and skills. You signed in with another tab or window. Alfonso Shimbel proposed the algorithm in 1955, but it is now named after Richard Bellman and Lester Ford Jr., who brought it out in 1958 and 1956. ) Here n = 7, so 6 times. % Step 3: Begin with an arbitrary vertex and a minimum distance of zero. {\displaystyle i\leq |V|-1} We have introduced Bellman Ford and discussed on implementation here.Input: Graph and a source vertex srcOutput: Shortest distance to all vertices from src. Total number of vertices in the graph is 5, so all edges must be processed 4 times. [1], Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. An example of a graph that would only need one round of relaxation is a graph where each vertex only connects to the next one in a linear fashion, like the graphic below: This graph only needs one round of relaxation. An Example 5.1. The following is the space complexity of the bellman ford algorithm: The space complexity of the Bellman-Ford algorithm is O(V). You can ensure that the result is optimized by repeating this process for all vertices. // processed and performs this relaxation to all of its outgoing edges. Parewa Labs Pvt. The Bellman-Ford algorithm, like Dijkstra's algorithm, uses the principle of relaxation to find increasingly accurate path length. The edges have a cost to them. The core of the algorithm is a loop that scans across all edges at every loop. Try hands-on Interview Preparation with Programiz PRO. This is one of the oldest Internet protocols, and it prevents loops by limiting the number of hops a packet can make on its way to the destination. dist[A] = 0, weight = 6, and dist[B] = +Infinity Using our Step 2, if we go back through all of the edges, we should see that for all \(v\) in \(V\), \(v.distance = distance(s, v)\). First, sometimes the road you're using is a toll road, and you have to pay a certain amount of money. This value is a pointer to a predecessor vertex so that we can create a path later. Modify it so that it reports minimum distances even if there is a negative weight cycle. Popular Locations. // This structure is equal to an edge. The third row shows distances when (A, C) is processed. We will use d[v][i] to denote the length of the Consider this graph, we're relaxing the edge. A version of Bellman-Ford is used in the distance-vector routing protocol. Sign up, Existing user? struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph)); graph->Vertex = Vertex; //assigning values to structure elements that taken form user. where \(w(p)\) is the weight of a given path and \(|p|\) is the number of edges in that path. Fort Huachuca, AZ; Green Valley, AZ | Each vertex is visited in the order v1, v2, , v|V|, relaxing each outgoing edge from that vertex in Ef. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. Remember that the distance to every vertex besides the source starts at infinity, so a clear starting point for this algorithm is an edge out of the source vertex.