the shortest paths from to every other vertex as well so there is no better algorithm (in the worst casefor finding the shortest path to single vertex than to find shortest paths to all vertices the algorithm described here will only compute the distance to every such vertexrather than recording the actual path recording the path requires modifications to the algorithm that are left as an exercise computer networks provide an application for the single-source shortest-paths problem the goal is to find the cheapest way for one computer to broadcast message to all other computers on the network the network can be modeled by graph with edge weights indicating time or cost to send message to neighboring computer for unweighted graphs (or whenever all edges have the same cost)the singlesource shortest paths can be found using simple breadth-first search when weights are addedbfs will not give the correct answer one approach to solving this problem when the edges have differing weights might be to process the vertices in fixed order label the vertices to vn- with when processing vertex we take the edge connecting and when processing we consider the shortest distance from to and compare that to the shortest distance from to to when processing vertex vi we consider the shortest path for vertices through vi- that have already been processed unfortunatelythe true shortest path to vi might go through vertex vj for such path will not be considered by this algorithm howeverthe problem would not occur if we process the vertices in order of distance from assume that we have processed in order of distance from to the first vertices that are closest to scall this set of vertices we are now about to process the ith closest vertexcall it shortest path from to must have its next-to-last vertex in thusd(sxmin ( (suw(ux)us in other wordsthe shortest path from to is the minimum over all paths that go from to uthen have an edge from to xwhere is some vertex in this solution is usually referred to as dijkstra' algorithm it works by maintaining distance estimate (xfor all vertices in the elements of are initialized to the value infinite vertices are processed in order of distance from whenever vertex is processedd(xis updated for every neighbor of figure shows an implementation for dijkstra' algorithm at the endarray will contain the shortest distance values there are two reasonable solutions to the key issue of finding the unvisited vertex with minimum distance value during each pass through the main for loop