Consider undirected graphs (with no weights). Often there are multiple shortest

Question

Consider undirected graphs (with no weights). Often there are multiple shortest paths between two nodes of a graph. For example, in a graph with vertices {1, 2, 3, 4, 5} and edges {(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)}, there are two shortest paths from 1 to 5: (1, 2, 4, 5), and (1, 3, 4, 5). Describe a linear-time algorithm such that, given an undirected, unweighted graph and two vertices u and v, the algorithm counts the number of distinct shortest paths from u to v. Justify its correctness and the running time.

Explanation / Answer

Algorithm to find number of shortest path between two vertices in a given undirected and unweighted graph G(V,E) where V=vertex set and E is edge set.

Perform BFS(Breadth first search) from one of given input vertex(u). At the time of BFS maintain an array of count[n] which count number of vertices at that level(IN WORST CASE THERE CAN BE N LEVELS) and initialize it to zero for all vertices.

Now, suppose during BFS, vertex x is popped from queue and we are pushing all adjacent non-visited vertices for next level iback into queue at the same time we should update count[i] = count of vertices at level i until we encounter destination vertex.

Finally, multiply from i=0 to i-1 value of count[i] gives the number of shortest paths between source vertex u and destination vertex v.

void count_shortest_path(int u,int v,int n)

// visited[n] for keeping track of visited

// node in BFS

bool visited[n] = {0};

// Initialize distances as 0

int count[n] = {0},level=0,node_count=0,indicator=0;

queue Q;

Q.push(u);

Q.push(-1);

count[level]=1;

visited[u] = true;

while (!Q.empty()&&indicator!=1)

{

int x = Q.front();

Q.pop();

//indicate levels and store no of nodes in current level

if(x==-1){

level++;

count[level]=node_count;

node_count=0;

Q.push(-1);

continue;

}

for (int i=0; i<edges[x].size(); i++)

{

if (visited[edges[x][i]])

continue;

node_count++;

Q.push(edges[x][i]);

visited[edges[x][i]] = 1;

if(i==v){

indicator=1;

break;

}

}

}

//print no of possible shortest path fron source node u to destination node v

int paths=1;

for(int i=0;i<=level;i++){

paths*=count[i];

}

cout<<"no of possible shortest path : "<<paths<<" ";

}

As Breadth first search is used for the algorithm ,therefore complexity will be O(V+E) as Graph is

represented using Adjacency List .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.