CareerCup

Apply Djikshtra's algorithm and keep track of number of times you update the destination node.

Create a Dictionary of Node to int, which will act as a counter. Perform a breadth first search starting from the source traversal, adding k to each node's counter as you process it (where k is the number of the currently processing nodes). The destination node's counter will be the number of paths to the node. Time is ~O(n), where n = number of edges. This doesn't check for cycles, however.

answer should be 7, isn't it?
15
125
1325
1235
135
1345
12345

“If there exists a cycle in a path from source to destination print Infinite path”
I don't get your point. If there is no cycle between source and destination, there must be only one path between them. Do you mean that we only consider the simple path?

1)create adjacency list from given connection
2)CreateQueue(),int count=0;
3)Enqueue(source)
4)while(!isQueueEmty)
{

int elem =Dequeue();
if(count&&elem=source){
print("loop");
exit;}
else if(elem==destination){
count++;
continue;
}
else{
for all w adjacent to elem{
Enqueue(w);
}
}//end else
}//end while

Ex:initial q 1,
then 2,3,5
then 5,3,3,5
then count=1 q= 3,3,5
then 5,4,3,5
then count =2 and q= 4,3,5
then 5,3,5
then count =3 q= 3 ,5
then 4,5,5
then 5,5,5
then count =4 q= 5,5
then count =5
then count =6
while loop done ,total path =count =6

#include<iostream>
#include<map>
#include <vector>
using namespace std;

#define SIZE 4

struct IntPairs
{
       int x;
       int y;       
}pairs[SIZE];

map<int, vector<int> > xMapy;
map<int, vector<int> >::iterator itr;
vector<int>::iterator vitr;

int CountPaths(int sourceNode, int destiNode);
     
void InitPairs()
{
     for(int i=0; i<SIZE; i++)
     {
             cout<<endl<<"For Pairs "<<i<<" Enter X: ";
             cin>>pairs[i].x;        
             cout<<"->";
             cin>>pairs[i].y;
     }
}


void GetPaths(int sourceNode, int destiNode)
{
     int countPaths = 0;
    
     for(int i=0; i<SIZE; i++)
     {
		 xMapy[pairs[i].x].push_back(pairs[i].y); 
     }
 
	 if((itr = xMapy.find(sourceNode)) != xMapy.end())
	 {
		for(int i = 0; i < itr->second.size(); i++)
		{
			countPaths += CountPaths(itr->second[i], destiNode);
		}
	 }
	 
	 cout<<"Total Paths: "<<countPaths<<endl;
}
    

int CountPaths(int sourceNode, int destiNode)
{
	if(sourceNode == destiNode)
	{
		return 1;
	}
		
	if(xMapy.find(sourceNode) == xMapy.end())
	{
		return 0;
	}
	else
	{
		for(int i = 0; i < xMapy.find(sourceNode)->second.size(); i++)
		{
			return CountPaths(xMapy.find(sourceNode)->second[i], destiNode);
		}
	}
}
	

int main()
{
    InitPairs();
    int sourceNode;
    int destiNode;
    cout<<"Enter source: ";
    cin>>sourceNode;
    cout<<endl<<" Enter Destination Node: "<<endl;
    cin>>destiNode;
    GetPaths(sourceNode, destiNode);
    return 0;
}

Beat this . Ruby rulz .

@path = [[1, 2],[1, 3],[1, 5],[2, 5],[2, 3],[3, 4],[3, 5],[4, 5]]

def pathExist(frm,dest,visited)
  puts  visited and return if frm == dest
  return if visited.length > 9
  @path.each do | st |
      pathExist(st.last,dest,visited + "-" + st.last.to_s) if st.first == frm
  end
end

This comment has been deleted.

tag

We need to fix backtracking with memorization. for the example given in the question if f(n) represents the number of paths from nth node. then f(1) = f(2)+f(3) + f(5) directly connected nodes.
f(1) = f(2)+f(3) + f(5)
f(1) = (f(3) + f(5)) + (f(4) + f(5)) + f(5)
f(1) = ((f(4) + f(5)) + f(5)) + (f(5) + f(5)) + f(5)
f(1) = ((f(5) + f(5)) + f(5)) + (f(5) + f(5)) + f(5) = 6 as f(5) = 1.
here we are calc f(3) twice which we can store and reduce calc

#define N 5
#define SRC 0
#define DST 4
int G[N][N}={{0,1,1,0,1},{0,0,1,0,1},{0,0,0,1,1},{0,0,0,0,1},{0,0,0,0,0}};    // Adjacency matrix
int path[N]={0,0,0,0,0}             // initialize number of paths to destination from each node 

int main(void)
{
            for(i=0;i<N; i++)
                  if(G[i][DST]==1)
                              path[i]++;


           for(i=0;i<N;i++)
          {
               for(j=0;j<N;j++)
               {
                        if(G[i][j]==1&&path[j]>0)
                                     path[i]=path[i]+path[j];
                }
         }
         print(path[SRC]);
}