weighted graphs in this minimum spanning tree with weighted graphs the shortest-path problem in the preceding we saw that graph' edges can have direction in this we'll explore another edge featureweight for exampleif vertices in weighted graph represent citiesthe weight of the edges might represent distances between the citiesor costs to fly between themor the number of automobile trips made annually between them ( figure of interest to highway engineerswhen we include weight as feature of graph' edgessome interesting and complex questions arise what is the minimum spanning tree for weighted graphwhat is the shortest (or cheapestdistance from one vertex to anothersuch questions have important applications in the real world we'll first examine weighted but non-directed graph and its minimum spanning tree in the second half of this we'll examine graphs that are both directed and weightedin connection with the famous dijkstra' algorithmused to find the shortest path from one vertex to another minimum spanning tree with weighted graphs to introduce weighted graphswe'll return to the question of the minimum spanning tree creating such tree is bit more complicated with weighted graph than with an unweighted one when all edges are the same weightit' fairly straightforward--as we saw in "graphs"--for the algorithm to choose one to add to the minimum spanning tree but when edges can have different weightssome arithmetic is needed to choose the right one the all-pairs shortest-path problem efficiency intractable problems