MINWALK - Editorial

dijkstra
easy-medium
editorial
graph
shortest-path

#1

PROBLEM LINK:

Practice

Contest

Author: Vaibhav Gosain

Tester: Sameer Gulati

Editorialist: Vaibhav Gosain

DIFFICULTY:

easy-medium

PREREQUISITES:

shortest path, Dijkstra Algorithm

PROBLEM:

Consider a weighted, undirected and connected graph with N nodes, numbered 1 to N, and M edges. Find the minimum cost of any walk from node S to node T , via node V, where cost of a walk is the sum of weights of distinct edges occurring in the walk.

EXPLANATION:

Suppose we take a path P1 from S to V , and a path P2 from V to T. There can be some common edges among these 2 paths. Suppose we reach node U after traversing the last edge in P2 which is common with P1. We can see that in the optimal case, all edges of P2 before node U must also lie in P1 because any other P2 will contribute more cost to the walk.

Hence, the optimal path will always have the following form:
for any node U, the walk consists of edges on the shortest path from S to U, from V to U, and from T to U.

Hence, if dist(a,b) is the cost of shortest path between node a and b, the required minimum cost walk will be:

min{ dist(S,U) + dist(V,U) + dist(T,U) } for all U

The Minimum distance of all nodes from S, T, and V can be found be doing Dijkstra from these 3 nodes.

Time complexity: O((N+M)*logN)

AUTHOR’S SOLUTION:

Author’s solution can be found here.