Shortest Path

Submitted By:
Mason

Difficulty:
Hard

Instructions:
Given a set of distances between pairs of locations, a source location, and a destination location, return an array of locations visited when traversing the shortest path between the source and destination locations. The source and destination locations should be included at the beginning and end of the visited locations list (respectively). The set of distances is represented as a hash of hashes. The key of the outer hash is the source location name, the key of the inner hash is the destination location name, and the value of the inner hash is the distance between those two points. Distances are single-direction distances; just because the distance from A to B is 4, you cannot assume that the distance from B to A is also 4. If a path does not exist between the source and destination locations passed to your method, return nil. If negative distances exist, don't try to find a shortest path (as it may be infinite). Simply return "Error: Negative Distances in Graph"

Hidden Code:
There is hidden code with assertions that is also being run to test out your code.

Code:
def shortest_path(graph, origin, destination)
    ___
end

graph = {
    "San Francisco" => {"Chicago" => 2132,
                        "Dallas" => 1734},
    "Chicago" => {"Durham" => 781},
    "Dallas" => {"Durham" => 1176}
}

assert_equal shortest_path(graph, "San Francisco", "Durham"), ["San Francisco", "Dallas", "Durham"]
assert_equal shortest_path(graph, "Durham", "San Francisco"), nil

Your Solution

Ruby 1.9.3

Back to Problems