Question

Describe and analyze an algorithm to determine the number of shortest paths from a source vertex s to a target vertex t in an arbitrary directed graph G with weighted edges. You may assume that all edge weights are positive and that all necessary arithmetic operations can be performed in O(1) time.

[Hint: Compute shortest path distances from s to every other vertex. Throw away all edges that cannot be part of a shortest path from s to another vertex. What’s left?]

Write a pseudo code algorithm for the situation described above. :)

Answer 1

algorithm:

d.assign(n, INF);

d[s] = 0;

set<pair<int, int>> q;

q.insert({0, s});

while (!q.empty())

{

int v = q.begin()->second;

q.erase(q.begin());

for (auto edge : adj[v])

{

int u = edge.first; int w = edge.second;

if (d[v] + w < d[u])

{

q.erase({d[u], u});

d[u] = d[v] + w;

q.insert({d[u], u});

}

}

}

pseudocode:-

#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{

int min = INT_MAX, min_index; // Initialize min value

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

}

void printSolution(int dist[])// A utility function to print the constructed distance array

void printSolution(int dist[])

{

printf("Vertex \t\t Distance from Source\n");

for (int i = 0; i < V; i++)

printf("%d \t\t %d\n", i, dist[i]);

}

// Function that implements Dijkstra's single source shortest path algorithm  for a graph represented using adjacency matrix representation

void dijkstra(int graph[V][V], int src)

{

int dist[V]; // The output array. dist[i] will hold the shortest

bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest

// path tree or shortest distance from src to i is finalized

for (int i = 0; i < V; i++)// Initialize all distances as INFINITE and stpSet[] as false

dist[i] = INT_MAX, sptSet[i] = false;

dist[src] = 0;// Distance of source vertex from itself is always 0

for (int count = 0; count < V - 1; count++)// Find shortest path for all vertices

{

int u = minDistance(dist, sptSet);// Pick the minimum distance vertex from the set of vertices not yet processed. u is always equal to src in the first iteration.

sptSet[u] = true;// Mark the picked vertex as processed

// Update dist value of the adjacent vertices of the picked vertex.

for (int v = 0; v < V; v++)

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX // Update dist[v] only if is not in sptSet, there is an edge from u to v, and total weight of path from src to v through u is smaller than current value of dist[v]

&& dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

}

// print the constructed distance array

printSolution(dist);

}

// driver program to test above function

int main()

{

/* Let us create the example graph discussed above */

int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },

{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },

{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;

}