pythonatSheriff
Full Stack Web Developer
The problem paragraph is :
((
Have the function GraphChallenge(strArr) take strArr which will be an array of strings which models a non-looping Graph. The structure of the array will be as follows: The first element in the array will be the number of nodes N (points) in the array as a string. The next N elements will be the nodes which can be anything (A, B, C .. Brick Street, Main Street .. etc.). Then after the Nth element, the rest of the elements in the array will be the connections between all of the nodes. They will look like this: (A-B, B-C .. Brick Street-Main Street .. etc.). Although, there may exist no connections at all.
An example of strArr may be: ["4","A","B","C","D","A-B","B-D","B-C","C-D"]. Your program should return the shortest path from the first Node to the last Node in the array separated by dashes. So in the example above the output should be A-B-D. Here is another example with strArr being ["7","A","B","C","D","E","F","G","A-B","A-E","B-C","C-D","D-F","E-D","F-G"]. The output for this array should be A-E-D-F-G. There will only ever be one shortest path for the array. If no path between the first and last node exists, return -1. The array will at minimum have two nodes. Also, the connection A-B for example, means that A can get to B and B can get to A.
Output: A-C-D-F
Input: new string[] {"4","X","Y","Z","W","X-Y","Y-Z","X-W"}
Output: X-W
Now, I have visited many topics that are talking about the (shortest path) like :
www.geeksforgeeks.org
www.geeksforgeeks.org
and many more. I've read the code and description but I think that my problem is a little bit easier than (BFS). I'll explain shortly, but first you've to look at my attached image to understand what I am thinking of. My idea is, if there is no consecutive two nodes, then we can ignore that edge or path and continue with the rest. For example, fro A to B, then from B to C, but after that cam A to C, then we can ignore the last two paths (A-B) and (B-C) and then continue with the rest of paths that way. So, all I need is to compare the two consecutive nodes with the joined paths. My starting code:
I'm not searching for a code, I just want to know if my approach to solve the problem is right or wrong? and if it's wrong, what is the right way ?
Thanks in advance.
((
Have the function GraphChallenge(strArr) take strArr which will be an array of strings which models a non-looping Graph. The structure of the array will be as follows: The first element in the array will be the number of nodes N (points) in the array as a string. The next N elements will be the nodes which can be anything (A, B, C .. Brick Street, Main Street .. etc.). Then after the Nth element, the rest of the elements in the array will be the connections between all of the nodes. They will look like this: (A-B, B-C .. Brick Street-Main Street .. etc.). Although, there may exist no connections at all.
An example of strArr may be: ["4","A","B","C","D","A-B","B-D","B-C","C-D"]. Your program should return the shortest path from the first Node to the last Node in the array separated by dashes. So in the example above the output should be A-B-D. Here is another example with strArr being ["7","A","B","C","D","E","F","G","A-B","A-E","B-C","C-D","D-F","E-D","F-G"]. The output for this array should be A-E-D-F-G. There will only ever be one shortest path for the array. If no path between the first and last node exists, return -1. The array will at minimum have two nodes. Also, the connection A-B for example, means that A can get to B and B can get to A.
Examples
Input: new string[] {"5","A","B","C","D","F","A-B","A-C","B-C","C-D","D-F"}Output: A-C-D-F
Input: new string[] {"4","X","Y","Z","W","X-Y","Y-Z","X-W"}
Output: X-W
Now, I have visited many topics that are talking about the (shortest path) like :
Shortest path in an unweighted graph - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
Breadth First Search or BFS for a Graph - GeeksforGeeks
Breadth First Search (BFS) is a graph traversal algorithm that explores vertices level by level, starting from a source node, and is used for various applications such as finding the shortest path in unweighted graphs, detecting cycles, and identifying connected components.
www.geeksforgeeks.org
my starting code to solve graph problem:
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class MainClass
{
public static void Main(string[] arg1)
{
string[] str = {"5","A","B","C","D","F","A-B","A-C","B-C","C-D","D-F"};
string source = str[1];
string destination = str.Last(i => i.Length <= 1);
var paths = from p in str
where p.Length > 1
select p;
}
}I'm not searching for a code, I just want to know if my approach to solve the problem is right or wrong? and if it's wrong, what is the right way ?
Thanks in advance.
Attachments
Last edited by a moderator:
