###### Asked in Computer ProgrammingMath and Arithmetic

Computer Programming

Math and Arithmetic

# Find Shortest path between two nodes in given graph?

## Answer

###### Wiki User

###### December 28, 2010 6:36PM

If u want 2 find shortest path between any 2 nodes

tak 1 source vertice and 1 destination vertice

the minimum number of vertices which comes while traversing from source to destination vertice will give you ur answer

that is,try to cover minimum o of vertices whil traversing.

## Related Questions

###### Asked in Graphs, C Programming

### What are the difference between graph and trees in c?

Graphs and trees are often used as synonyms for lattices or
networks of interlinked nodes. A graph is the more general term and
essentially covers all types of lattices and networks including
trees, while a tree is a more specific type of graph, not unlike a
family tree extending downwards much like the roots of a tree. A
binary tree is a typical example of a tree-like graph.
Non-tree-like graphs are typically used to model road maps and thus
help solve travelling salesman problems, such as finding the
shortest or fastest route between a given set of nodes. Real-life
computer networks can also be modelled using graphs. And unlike
trees which are two-dimensional structures, graphs can be
multi-dimensional.

###### Asked in Science, Math and Arithmetic

### Generally What is meant by graph?

'Graph' comes from a Greek word meaning 'write', so it relates
to things that appear on paper or on screen.
The answer really depends on the context. For instance in
computer science a graph is a set of nodes and edges that go
between the nodes. In other subjects it may mean a diagram
representing the relationship between two sets of numbers, often
the input and output of a function. In other contexts it may mean a
pictorial chart...

###### Asked in Math and Arithmetic

### What is dense graph and sparse graph?

Sparse vs.
Dense Graphs
Informally, a graph with relatively few edges is sparse, and
a graph with many edges is dense. The following definition
defines precisely what we mean when we say that a graph ``has
relatively few edges'':
Definition (Sparse Graph) A sparse graph is a
graph in which .
For example, consider a graph with n nodes. Suppose that
the out-degree of each vertex in G is some fixed constant
k. Graph G is a sparse graph because .
A graph that is not sparse is said to be dense:
Definition (Dense Graph) A dense graph is a graph
in which .
For example, consider a graph with n nodes. Suppose that
the out-degree of each vertex in G is some fraction f
of n, . E.g., if n=16 and f=0.25, the
out-degree of each node is 4. Graph G is a dense
graph because .

###### Asked in Science, Jobs & Education

### Difference between node and keypoint in EFA?

Keypoints - Keypoints are merely geometric constructions that we
create while creating a geometric model of the given problem.
Nodes - nodes are obtained after the we complete the meshing
operation. they are a part of the fea model. These are the points
where the desired values are obtained. Also nodes are the points
where the loads are applied.

###### Asked in Computer Programming, Math and Arithmetic

### What is the difference between Dijkstra's algorithm and Floyd's algorithm?

My (shallow) understanding is that while in Dijkstra you are
trying to find the shortest path from a starting node to a given
destination, in Floyd's you looking for the shortest path between
any pair of nodes. The other major difference is that in Dijkstra
you are not allowed to have negative weights/costs while you are
allowed to have negative weights in Floyd. In the end they achieve
the same objective if you wish to move from node A to node Z the
main difference is that in Floyds you probably use the principle of
dynamic programming(?).

###### Asked in Computer Networking, Computer Programming, Math and Arithmetic

### Difference between Dijkstra's algorithm and Floyd's algorithm?

Dijkstra doesn't support negative weight-age, Floyd support
negative edges but no negative cycles. Dijkstra running time is v2
and Floyd has v3.Dijkstra is fast compared to Floyd, because only
find the shortest path for single node. Floyd Slow as compared to
Dijkstra.
Dijkstra's Algorithm<?xml:namespace prefix
= o ns = "urn:schemas-microsoft-com:office:office" />
Notation:
Di = Length of shortest path from node 'i' to node 1.
di,j = Length of path between nodes i and j .
Algorithm
Each node j is labeled with Dj, which is an estimate of cost of
path from node j to node 1. Initially, let the estimates be
infinity, indicating that nothing is known about the paths. We now
iterate on the length of paths, each time revising our estimate to
lower values, as we obtain them. Actually, we divide the nodes into
two groups ; the first one, called set P contains the nodes whose
shortest distances have been found, and the other Q containing all
the remaining nodes. Initially P contains only the node 1. At each
step, we select the node that has minimum cost path to node 1. This
node is transferred to set P. At the first step, this corresponds
to shifting the node closest to 1 in P. Its minimum cost to node 1
is now known. At the next step, select the next closest node from
set Q and update the labels corresponding to each node using :
Dj = min [ Dj , Di + dj,i ]
Finally, after N-1 iterations, the shortest paths for
all nodes are known, and the algorithm terminates.
Principle
Let the closest node to 1 at some step be i. Then i is shifted
to P. Now, for each node j , the closest path to 1 either passes
through i or it doesn't. In the first case Dj remains the same. In
the second case, the revised estimate of Dj is the sum Di + di,j .
So we take the minimum of these two cases and update Dj
accordingly. As each of the nodes get transferred to set P, the
estimates get closer to the lowest possible value. When a node is
transferred, its shortest path length is known. So finally all the
nodes are in P and the Dj 's represent the minimum costs. The
algorithm is guaranteed to terminate in N-1 iterations and its
complexity is O( N2 ).
The Floyd Warshall Algorithm
This algorithm iterates on the set of nodes that can be
used as intermediate nodes on paths. This set grows from a single
node ( say node 1 ) at start to finally all the nodes of the graph.
At each iteration, we find the shortest path using given set of
nodes as intermediate nodes, so that finally all the shortest paths
are obtained.
Notation
Di,j [n] = Length of shortest path between the nodes i and j
using only the nodes 1,2,....n as intermediate nodes.
Initial Condition
Di,j[0] = di,j for all nodes i,j .
Algorithm
Initially, n = 0. At each iteration, add next node to n. i.e.
For n = 1,2, .....N-1 ,
Di,j[n + 1] = min { Di,j[n] , Di,n+1[n] + Dn+1,j[n] }
Principle
Suppose the shortest path between i and j using nodes 1,2,...n
is known. Now, if node n+1 is allowed to be an intermediate node,
then the shortest path under new conditions either passes through
node n+1 or it doesn't. If it does not pass through the node n+1,
then Di,j[n+1] is same as Di,j[n] . Else, we find the cost of the
new route, which is obtained from the sum, Di,n+1[n] + Dn+1,j[n].
So we take the minimum of these two cases at each step. After
adding all the nodes to the set of intermediate nodes, we obtain
the shortest paths between all pairs of nodes together. The
complexity of Floyd-Warshall algorithm is O ( N3 ).

###### Asked in Civil Engineering, Bridges and Tunnels, The Difference Between

### What is the difference between Local Bridge and Remote Bridge?

Local bridges are ties between two nodes in a social graph that
are the shortest (and often the only plausible) route by which
information might travel from those connected to one to those
connected to the other. [2] Local bridges differ from regular
bridges in that the end points of the local bridge cannot have a
tie directly between them and should not share any common
neighbors.
never found any answers in answers. sucks

###### Asked in Math and Arithmetic

### What the definition of circuit in math?

Graph theory - a mathematical circuit requires a)transportation
between nodes (points) b) w/o returning to the original node via a
line segment already used. The most simplistic circuit in math
would be three nodes (a triangle, containg six unique pathways).
One line seg (2 nodes) has 2 pathways but both violate b) QED