if there is another shortest path will it be the second shortest path?

http://en.wikipedia.org/wiki/Yen's_algorithm

How about this?

Can you post the statement because I can't open UVa now, please? Is the graph directed? Can the path contain cycles?

PS: Am I the only one who cannot open UVa?

Hello again! I just got accepted, let me explain my idea not only for the second but for the K-th shortest path in a graph:

We are going to use a modified Dijkstra's algorithm. We will store vectors for each node containing the distances(instead of an array dist[i] for each node i).

Assume that we are using the standard Dijkstra's algorithm implemented with a priority queue. We will use this structure for the queue:

struct el
{
    int vertex,cost;
    el(){}
    el(int a, int b)
    {
        vertex=a;
        cost=b;
    }
    bool operator<(const el &a) const
    {
        return cost>a.cost;
    }
};

At each step we take the element on the top of the queue. We will push the current distance in the vector in two cases:

1) If the vector with the distances is empty

or

2) If the vector has one element inside and the current distance is greater than the first:

curr=pq.top();
pq.pop();
if(dist[curr.vertex].size()==0)
    dist[curr.vertex].push_back(curr.cost);
else if(dist[curr.vertex].back()!=curr.cost)
    dist[curr.vertex].push_back(curr.cost);

Then we go through curr.vertex's children. If the current children has already have two elements in its vector, then we skip it. Otherwise, we find the current distance to reach it from curr.vertex and push it in the queue.

My code is here: http://ideone.com/QpWFnR

But the thing is nobody has mentioned any algorithm for All-Pair Second Shortest Path problem yet.

All-pair shortest path can be done running N times Dijkstra's algorithm. Then all-pair second shortest paths can be done running N times the modified Dijkstra's algorithms. The complexity is O(2*(V*logV + E)) = O(V*logV + E) per run which is the same as the normal Dijkstra.

Is that what are you asking?