Explore BrainMass

weighted directed graph

Give an example of a weighted directed graph with at most 5 vertices such that Dijkstra's algorithm will NOT give the correct results for the shortest path lengths from source s to every other vertex. Your graph may have negative edge weights but NO negative weight cycles. Indicate what answer Dijkstra's algorithm would give and what the correct answer should be.

Solution Summary

An example of a weighted directed grap is given.