notes therefore we shall havetable adjacency list structure for graph in figure note that adjacent vertices may appear in the adjacency list in arbitrary order also an arrow from to in the list linked to does not mean that and are adjacent the adjacency list representation is better for sparse graphs because the space required is ( )as contrasted with the ( required by the adjacency matrix representation shortest path algorithms dijkstra developed an algorithm to determine the shorted path between two nodes in graph it is also possible to find the shortest paths from given source node to all nodes in graph at the same timehence this problem is sometimes called the single-source shortest paths problem the shortest path problem may be expressed as followsgiven connected graph (ve)with weighted edges and fixed vertex in vto find shortest path from to each vertex in the weights assigned to the edges may represent distancecosteffort or any other attribute that needs to be minimized in the graph solution to this problem could be found by finding spanning tree of the graph the graph representing all the paths from one vertex to all the others must be spanning tree it must include all vertices there will also be no cycles as cycle would define more than one path from the selected vertex to at least one other vertex the algorithm finds the routesby cost precedence let' assume that every cost is positive number the algorithm is equally applicable to grapha digraphor even to mixed graph with only some of its sides directed if we consider digraphthen every other case is fully covered as well since no directed side can be considered directed sides of equal cost for every direction the algorithm is based on the fact that every minimal path containing more than one side is the expansion of another minimal path containing side less this happens because all costs are considered as positive numbers in this way the first route ( found by the algorithm will be one arc routethat is from the starting point to one of the sides directly connected to this starting point the next route ( will be one arc route itselfor two arc routebut in this case will be an expansion of ( lovely professional university