PROBLEM LINK:Author: Devendra Agarwal DIFFICULTY:MediumHard. PREREQUISITES:Dijkstra Algorithm, STL uses. PROBLEM:You are given a graph, you need to find the shortest walk in the graph from src to snk which satisfies the following property: Let the shortest path from src to snk goes from edges $E_{1} > E_{2} > \cdots > E_{k}$ , then $Weight(E_{1}) > Weight(E_{2}) < Weight(E_{3}) > Weight(E_{4}) \cdots$ and so on. QUICK EXPLANATION:The given problem can be solved using few modification in Dijkstra Algorithm. EXPLANATION:First Subproblem: Given a graph, You need to find the shortest path in the graph from $\text{src}$ to $\text{snk}$, without any condition. This problem can be solved using Dijkstra Algorithm. In Dijkstra Algorithm, We initialize distance of the $\text{src}$ with $0$, and distance of other vertices as $ \infty$ and add $\text{src}$ into a priority queue, and we do it in following manner.
The given pseudocode calculates the shortest path for each of the vertex. The shortest path for the $\text{snk}$ can be reported easily. Implementation of the Dijkstra Algorithm can be looked here.
You are given a graph, you need to find the shortest wak in the graph from src to snk which satisfies the following property: Let the shortest path from src to snk goes from edges $E_{1} > E_{2} > \cdots > E_{k}$ , then $Weight(E_{1}) < Weight(E_{2}) < Weight(E_{3}) < Weight(E_{4}) \cdots$ and so on. In subproblem 1, we kept a visited array. Once a node has been visited, we get the shortest path for that particular node and there is no need to visit the same vertex again. We can do it in a different manner, at the moment we are exploring vertex $v$, and pushing all neighbour of $v$ in the priority queue, we can delete all neighbouring edges of vertex $v$ just after pushing them in priority queue. So, for solving subproblem 2, Consider we have arrived at vertex $V$ by an edge having weight $W$. when removing the vertex $V$ from the priority queue, push all neighbour $X$ of $V$ if $ W_{VX} > W$, and delete all those edges from the edgelist . This algorithm guarantees that each edge is processed at most once. hence, algorithm will terminate. We may visit a vertex more than once. The proof of correctness of the given algorithm can be understood in following way. If we arrived at vertex $V$ with cost $C_{1}$, and later we arrived at same vertex with cost $C_{2}$, then $C_{1} < C_{2}$, cost of last explored edge in both cases are the same . Implementation details: Preprocess the graph by sorting outgoing edges from each node (by weight). Keep a pointer at each vertex, which will tell edges having higher weight should not be considered. Original Problem: To solve the original problem, where edge length is increasing and decreasing alternatively. We need to make a few changes in second subproblem. We will keep two copies of the graph in as the edge list, Call them $GL$ and $GS$. A $ \text{counter}$ should be kept, $ \text{even counter}$ will denote that we are looking for a smaller edge and $ \text{odd counter}$ will tell that we are looking for a larger edge than previous one.While we are looking for a larger edges we will delete those larger edges after pushing them in the priority queue.This deletion will happen only in larger copy of the graph which is edgelist $GL$, and similarly in other case. The reason for keeping two copies of graph is that if edge $E$ has been taken and it is larger than last one, then later it can considered again(as shorter than last one). Now see the reason of keeping two copies of graph, edge having length $10$ is being considered twice. During execution of the algorithm, first it will be deleted from the smaller copy of the graph i.e. $GS$(while traversing from length $200$ to $10$)and later it will be deleted from the larger copy of the graph i.e. $GL$(while traversing for length $8$ to $10$). As the deletion can be costly or can have linear complexity, we can keep counters which will tell range in which edge list need to be considered. Time Complexity of the above approach will be $O(ElogE + ElogV)$, $O(ElogE)$ will appear due to sorting edge list, and $O(ElogV)$ due to Dijkstra. Solutions:Setter's solution can be found here. asked 11 Feb '15, 00:50

1 st test case is wrong. there is no path from 1 to 4 it should be 4 to 1 6. then only answer is possible. answered 16 Feb '15, 18:40
