# Shortest Path-Some interesting shortest path questions

Shortest Path Some interesting shortest path questions The shortest path may change. The reason is, there may be different number of edges

Question 1: Given a directed weighted graph. You are also given the shortest path from a source vertex ‘s’ to a destination vertex ‘t’.  If weight of every edge is increased by 10 units, does the shortest path remain same in the modified graph?
The shortest path may change. The reason is, there may be different number of edges in different paths from s to t. For example, let shortest path be of weight 15 and has 5 edges. Let there be another path with 2 edges and total weight 25. The weight of the shortest path is increased by 5*10 and becomes 15 + 50. Weight of the other path is increased by 2*10 and becomes 25 + 20. So the shortest path changes to the other path with weight as 45.

Question 2: This is similar to above question. Does the shortest path change when weights of all edges are multiplied by 10?
If we multiply all edge weights by 10, the shortest path doesn’t change. The reason is simple, weights of all paths from s to t get multiplied by same amount. The number of edges on a path doesn’t matter. It is like changing unit of weights.

Question 3: Given a directed graph where every edge has weight as either 1 or 2, find the shortest path from a given source vertex ‘s’ to a given destination vertex ‘t’. Expected time complexity is O(V+E).
If we apply Dijkstra’s shortest path algorithm, we can get a shortest path in O(E + VLogV) time. How to do it in O(V+E) time? The idea is to use BFS . One important observation about BFS is, the path used in BFS always has least number of edges between any two vertices. So if all edges are of same weight, we can use BFS to find the shortest path. For this problem, we can modify the graph and split all edges of weight 2 into two edges of weight 1 each. In the modified graph, we can use BFS to find the shortest path. How is this approach O(V+E)? In worst case, all edges are of weight 2 and we need to do O(E) operations to split all edges, so the time complexity becomes O(E) + O(V+E) which is O(V+E).

Question 4: Given a directed acyclic weighted graph, how to find the shortest path from a source s to a destination t in O(V+E) time?
See: Shortest Path in Directed Acyclic Graph

## C++ Programming – Program to add two polynomials

C++ Programming – Program to add two polynomials – Mathematical Algorithms – Addition is simpler than multiplication of polynomials. We initialize result

## C programming-Lucky Numbers

C programming-Lucky Numbers – Mathematical algorithms – Lucky numbers are subset of integers. let us see the process of arriving at lucky numbers.

## Add 1 to a given number

Add 1 to a given number – Bit Algorithm – Add 1 to a given number write a program to add 1 to a given number. You are not allowed to use operators like ‘+’,

## C Program-Swap two nibbles in a byte

C Program Swap two nibbles in a byte – Bit Algorithm – A nibble is a four-bit aggregation, or half an octet. There are two nibbles in a byte.

## Worst Average and Best Cases

We will take an example of Linear Search and analyze it using Asymptotic analysis.We can have three cases to analyze an algorithm:Worst,Average,Best

## C Programming – Subset Sum Problem

C Programming – Subset Sum Problem – Dynamic Programming Given a set of non-negative integers, and a value sum, determine if there is a subset