added and processed note that with both breadth first and depth firstthe order of the vertices depends on the implementation there is no reason why ' neighbour should be visited before in the example so it is better to speak of result of depth first or breadth first traversalrather than of the result note also that the only vertices that will be listed are those in the same connected component as if we have to ensure that all vertices are visitedwe may need to start the traversal process with number of different starting verticeseach time choosing one that has not been marked as done when the previous traversal terminated exerciseswrite algorithmsin pseudocodeto ( visit all nodes of graphand ( decide whether given graph is connected or not for ( you will actually need two algorithmsone for the strong notion of connectednessand another for the weak notion shortest paths dijkstra' algorithm common graph based problem is that we have some situation represented as weighted digraph with edges labelled by non-negative numbers and need to answer the following questionfor two particular verticeswhat is the shortest route from one to the otherhereby "shortest routewe mean path whichwhen we add up the weights along its edgesgives the smallest overall weight for the path this number is called the length of the path thusa shortest path is one with minimal length note that there need not be unique shortest pathsince several paths might have the same length in disconnected graph there will not be path between vertices in different componentsbut we can take care of this by using once again to stand for "no path at allnote that the weights do not necessarily have to correspond to distancesthey couldfor examplebe time (in which case we could speak of "quickest paths"or money (in which case we could speak of "cheapest paths")among other possibilities by considering "abstractgraphs in which the numerical weights are left uninterpretedwe can take care of all such situations and others but notice that we do need to restrict the edge weights to be nonnegative numbersbecause if there are negative numbers and cycleswe can have increasingly long paths with lower and lower costsand no path with minimal cost applications of shortest-path algorithms include internet packet routing (becauseif you send an email message from your computer to someone elseit has to go through various email routersuntil it reaches its final destination)train-ticket reservation systems (that need to figure out the best connecting stations)and driving route finders (that need to find an optimum route in some sensedijkstra' algorithm in turns out thatif we want to compute the shortest path from given start node to given end node zit is actually most convenient to compute the shortest paths from to all other nodesnot just the given node that we are interested in given the start nodedijkstra' algorithm computes shortest paths starting from and ending at each possible node it maintains all the information it needs in simple arrayswhich are iteratively updated until the solution is reached because the algorithmalthough elegant and shortis fairly complicatedwe shall consider it one component at time overestimation of shortest paths we keep an array of distances indexed by the vertices the idea is that [zwill hold the distance of the shortest path from to when