Counting shortest paths in a non-directed graph using BFS

  • MHB
  • Thread starter evinda
  • Start date
In summary, the conversation discusses an algorithm for calculating the number of shortest paths between two nodes in a given non-directed graph. The algorithm uses BFS and should run in $O(n+m)$ time for a graph with $n$ vertices and $m$ edges. The speaker suggests trying to implement the algorithm and measuring its complexity.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

A non-directed graph $G=(V,E)$ and two nodes $v$ and $u$ of $G$ are given. Give an algorithm that calculates the number of shortest paths $v-u$ in $G$. (The algorithm doesn't have to print all the paths, just how many exist.) The algorithm should run in time $O(n+m)$ for a graph with $n$ vertices and $m$ edges. Is it like that?

We apply BFS. At the point where we add the nodes in the queue, we calculate also the number of nodes.
 
Technology news on Phys.org
  • #2
What do you think? Have you tried implementing it to see if it sort of works, try and measure the complexity, ...?
 

FAQ: Counting shortest paths in a non-directed graph using BFS

What is the concept of "Number of paths" in science?

The concept of "Number of paths" in science refers to the number of different routes or ways that an object or energy can take in a given system or environment. It is a measure of the variability or complexity of a system.

How is the number of paths calculated in science?

The number of paths is calculated by analyzing the different possible combinations and arrangements of elements in a system. This can involve mathematical formulas or computer simulations to determine all the potential paths that an object or energy can take.

What is the significance of the number of paths in scientific research?

The number of paths is an important factor in scientific research as it can provide insights into the behavior and interactions of objects or energy in a system. It can also help scientists understand the complexity of a system and make predictions about its future behavior.

How does the number of paths impact real-world applications?

In real-world applications, the number of paths can influence the efficiency and effectiveness of systems. For example, in transportation systems, the number of paths can affect traffic flow and the time it takes for a person or vehicle to reach their destination.

Are there any limitations to using the number of paths in scientific analysis?

While the number of paths can provide valuable information, it is important to note that it is not the only factor to consider in scientific analysis. Other variables and factors such as external influences and random events can also impact the behavior of a system. Therefore, the number of paths should be used in conjunction with other tools and methods in scientific research.

Similar threads

MHB Find path to minimum cost from start to finish
Replies
19
Views
2K
MHB Show that the Dijkstra's algorithm computes correctly the shortest paths
Replies
1
Views
2K
Python BFS Shortest Distance of Graph Calculation in Python
Replies
1
Views
5K
MHB Assign integers to the vertices of G
Replies
1
Views
1K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
Replies
4
Views
1K
I Traffic simulation : directed graph including specific rules
Replies
5
Views
1K
MHB Find the greatest of the shortest paths
Replies
7
Views
2K
MHB How can the time complexity be achieved?
Replies
1
Views
1K
MHB Find Algorithm for O(V*E) Transitive Closure of a Graph
Replies
11
Views
3K
Comp Sci Shortest path problem in bipartite graph
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top