Re: [algogeeks] graphs
wouldn't a modified dijkstra do the trick?? On 4/2/11, Tech id ilovea...@gmail.com wrote: Given a directed graph G, with V vertices and E edges. Each edge in E is associated with a real number ‘r’,a reliabilty factor with r between 0(exclusive) and 1(inclusive). You are also given a pair of nodes u and v. Find the most reliable path in the given graph from u to v. Input will be the graph represented as a matrix with the following format: * the number of vertices n. (therefore, A is an nxn matrix) * The elements of A, row-wise: (total n*n numbers) A(i,j) = 0 denotes that the edge (i,j) is not present A(i,j) between 0 (exclusive) and 1 (inclusive) indicates that the edge (i,j) is present with reliability A(i,j). Output: Your output will be a sequence of vertices giving the path from u to v such as 1,4,3,5,8,6,7 with u=1 and v=7. The output is thus a comma separated list of vertices giving the path from u to v. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] graphs
QUESTION : input a number C , an output all of the ways that a group of ascending positive numbers can be summed to give C. for e.g if C=6,the output should be 1+2+3 1+5 2+4 [solve using dynamic programming] please tell me about this..d -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] graphs
Given a directed graph G, with V vertices and E edges. Each edge in E is associated with a real number ‘r’,a reliabilty factor with r between 0(exclusive) and 1(inclusive). You are also given a pair of nodes u and v. Find the most reliable path in the given graph from u to v. Input will be the graph represented as a matrix with the following format: * the number of vertices n. (therefore, A is an nxn matrix) * The elements of A, row-wise: (total n*n numbers) A(i,j) = 0 denotes that the edge (i,j) is not present A(i,j) between 0 (exclusive) and 1 (inclusive) indicates that the edge (i,j) is present with reliability A(i,j). Output: Your output will be a sequence of vertices giving the path from u to v such as 1,4,3,5,8,6,7 with u=1 and v=7. The output is thus a comma separated list of vertices giving the path from u to v. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Graphs...
In a DAG, print the maximal paths Can any one help me out with this question...? I don seem to understand the question itself... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Graphs...
graph diameter? On Mon, Sep 6, 2010 at 6:34 AM, Maria lydwin.ma...@gmail.com wrote: In a DAG, print the maximal paths Can any one help me out with this question...? I don seem to understand the question itself... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Graphs...
the longest one among all vertice pairs' shortest paths. On Mon, Sep 6, 2010 at 11:09 AM, Yan Wang wangyanadam1...@gmail.com wrote: graph diameter? On Mon, Sep 6, 2010 at 6:34 AM, Maria lydwin.ma...@gmail.com wrote: In a DAG, print the maximal paths Can any one help me out with this question...? I don seem to understand the question itself... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Graphs.
int count=0; for every vertex v{ if visited[v]==0 dfs(v) count++; } count is the number of components in graph or m i missing something ? On Fri, Jul 9, 2010 at 9:23 PM, amit amitjaspal...@gmail.com wrote: How to check if a directed graph is connected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] graphs again
A graph is given. You need to design a data structure with minimum space complexity such that it does the follows -- Finds whether nodes u and v have a path in between them in O(1) time. -- Finds whether there is a path of length k between u and v in O(k) time. The same data structure to be used for both the purposes. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] graphs again
i would prepare the transitivity matrix while inserting the edge into the matrix the search then would be a O(1) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 4, 2010 at 3:15 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: A graph is given. You need to design a data structure with minimum space complexity such that it does the follows -- Finds whether nodes u and v have a path in between them in O(1) time. -- Finds whether there is a path of length k between u and v in O(k) time. The same data structure to be used for both the purposes. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.