Graph - table of contents

1. 2nd best shortest path.
2. Articulation Point and Bridge finding

Articulation Point and Bridge Finding

Samiul vaia's Blog:

1. Articulation Point
2. Bridge finding

Others:

1. http://www.geeksforgeeks.org/bridge-in-a-graph/
2. http://www.shafaetsplanet.com/planetcoding/?p=2504
3. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

2nd best shortest path

Well this problem is really an interesting one.Determining the shortest path is very easy using dijkstra's Algorithm.But to determine the 2nd best shortest path needs more pruning.

To solve this I mainly followed the lead of this blog post. This problem can be solved by modifying the standard dijkstra's Algorithm.

We will maintain a 2d vector of Distance array rather than 1D Distance array.

A distance will be pushed in two cases:
1. if the size of the distance arraylist of current vertex is zero. that certainly implies this is the shortest cost so far of this vertex.So we will push it into the list of that vertex.
2.if the size is one and the current distance is greater than the existing one. so that makes this as the 2nd best distance.

As the dijkstra's algorithm works greedily , so the elements of the list of any vertex is certainly the shortest distances. So if any vertex has already two elements in its list so we just skip it.


Problem links:
uva-always late
lightoj-not the best

Implementation:
http://ideone.com/QpWFnR

K-best shortest path:
https://en.wikipedia.org/wiki/Yen%27s_algorithm

(I will update this as soon as i get time to implement it by myself :P )