CODEWITHSUNDEEP
algorithmgraphgraph-algorithmshortest-pathdijkstra
סמי זלדין
סמי זלדין

Reputation: 13

Shortest path from cities to gas stations (No fuel, but roads are weighted)

In a directed graph with weights on the edges, representing the length of the different roads between nodes. Some of the nodes are gas stations, the others are cities. How can I find the closest gas station to each city? There is no issue with fuels. The weights are just the lengths of the roads between nodes.

I thought of using Dijkstra from every single node that is not a gas station (N1,N2,...) and by having a key to each node of "True", "False", having true if it is a gas station (G1,G2,...,), then return the closest node (Ni) with key "True", to some Gas Station (Nj).

Not sure about the complexity. It seems like O(Dijkstra * size of (N1,N2,...)), and then for each Ni, go linearly over the array and return the smallest node with "True" key. Not sure if this is a valid way, I'd like to get some help and perhaps something that is more efficient.

Upvotes: 0

Views: 476

Answers (1)

Roman Svistunov
Roman Svistunov

Reputation: 1079

This problem can be solved using just one run of the Dijkstra algorithm, but with a twist. While usually when implementing Dijkstra you set zero distance only to one vertex you start with, to solve this problem you set it for all your gas stations' vertices. Thus, you also need to add these zero-distance vertices to the priority queue (heap) at the initialization. Apart from the initialization algorithm stays the same.

Upvotes: 2

Related Questions