I have a graph problem to solve and I'm wondering if my approaching technique is right?

pythonatSheriff

Full Stack Web Developer
Joined
Dec 15, 2021
Messages
25
Location
Egypt
Programming Experience
1-3
Twitter
shiccorama
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.

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 :
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:
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

  • WhatsApp Image 2021-12-19 at 9.00.03 PM.jpeg
    WhatsApp Image 2021-12-19 at 9.00.03 PM.jpeg
    42.8 KB · Views: 37
  • WhatsApp Image 2021-12-19 at 9.00.03_PM.jpeg
    WhatsApp Image 2021-12-19 at 9.00.03_PM.jpeg
    52 KB · Views: 36
Last edited by a moderator:
Solution
You are just trying to do a premature optimization that will actually just make the code more complicated rather than simpler. Yes, trying to find those shortcuts or skips may give you a shortcut ... but only if they exist. Think about it, if you are looking for the shortcuts, then you would go through the adjacency list first looking for connections from Node[1] to Node[n]. If you find it great. If not, then you start looking for Node[1] to Node[n-1]. If you find it, then you'll have to go over the adjacency list again looking for Node[n-1] to Node[n] to make the last hop. If it exist, yay! You have a solution: Node[1]-Node[n-1]-Node[n]. If it doesn't exist, then you'll next have to look for Node[1] to Node[n-2]. If you find it, then...

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,085
Location
Chesapeake, VA
Programming Experience
10+
You are just trying to do a premature optimization that will actually just make the code more complicated rather than simpler. Yes, trying to find those shortcuts or skips may give you a shortcut ... but only if they exist. Think about it, if you are looking for the shortcuts, then you would go through the adjacency list first looking for connections from Node[1] to Node[n]. If you find it great. If not, then you start looking for Node[1] to Node[n-1]. If you find it, then you'll have to go over the adjacency list again looking for Node[n-1] to Node[n] to make the last hop. If it exist, yay! You have a solution: Node[1]-Node[n-1]-Node[n]. If it doesn't exist, then you'll next have to look for Node[1] to Node[n-2]. If you find it, then you need to look for Node[n-2] to Node[n], or Node[n-2] to Node[n-1] and then Node[n-1] to Node[n]. ...

The beauty of Djikstra's algorithm is its simplicity:
What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.

— Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001[5]
 
Solution

pythonatSheriff

Full Stack Web Developer
Joined
Dec 15, 2021
Messages
25
Location
Egypt
Programming Experience
1-3
Twitter
shiccorama
You are just trying to do a premature optimization that will actually just make the code more complicated rather than simpler. Yes, trying to find those shortcuts or skips may give you a shortcut ... but only if they exist. Think about it, if you are looking for the shortcuts, then you would go through the adjacency list first looking for connections from Node[1] to Node[n]. If you find it great. If not, then you start looking for Node[1] to Node[n-1]. If you find it, then you'll have to go over the adjacency list again looking for Node[n-1] to Node[n] to make the last hop. If it exist, yay! You have a solution: Node[1]-Node[n-1]-Node[n]. If it doesn't exist, then you'll next have to look for Node[1] to Node[n-2]. If you find it, then you need to look for Node[n-2] to Node[n], or Node[n-2] to Node[n-1] and then Node[n-1] to Node[n]. ...

The beauty of Djikstra's algorithm is its simplicity:
ok, I get it, that's cool, I will read carefully Dijkstra's algorithm and try to apply it. Thanks a million.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,085
Location
Chesapeake, VA
Programming Experience
10+
Out of curiosity, where are you getting all these "challenges" that you are working on? It's kind of strange for them to be asking questions that great CS questions, but then at the same time not following best practices like being "stringly" typed and using Hungarian naming conventions in C# code.
 
Top Bottom