Hi, i am trying to make an algorithm that will read the nodes of a graph. Then i should find the shortest path that i have to follow in order to pass from all the nodes.
I am trying to make it so the algorithm will calculate every possible path and then it will output the shortest.
Is there any way to make an algorithm to calculate this?
Thanks in advance.
Every possible path?! How about the most likely paths, and obtain the shortest of those?
Ok, but how can i find the most likely paths?
Ok, but how can i find the most likely paths?
You have to define "most likely path" and decide whether it is pertinent to your needs. If you need to find THE shortest path, it isn't. There is a wealth of information on Shortest Path problems out there. You need to figure out which one best applies to your particular needs. For a small number of nodes and paths, the "dumb" brute-force method is best. Calculate all the paths and pick the shortest. For a large number of nodes and paths, you need a "smarter" algorithm, one that doesn't duplicate calculations. Dijkstra's Algorithm is often a good one, but there is no "one size fits all" algorithm.
For a small number of nodes and paths, the "dumb" brute-force method is best. Calculate all the paths and pick the shortest.
Can anyone help me to make an algorithm that will calculate each possible path and will pick the shortest like the brute-force method?
Can anyone help me to make an algorithm that will calculate each possible path and will pick the shortest like the brute-force method?
Yes, many of us can. If you want a more specific answer, you are going to have to ask a more specific question.
Yes, many of us can. If you want a more specific answer, you are going to have to ask a more specific question.
I will tell you more information.
There are some nodes on a graph.
I start always from (0,0).
I should go to the node with the biggest x and then to return to (0,0) in the shortest cycle. In this path i have to pass from all the nodes.
As i go to the node with biggest x i should always go toward x axes (xprevious<xnext) and as i return (xnext<xprevious).
I have to find the shortest path to make this cycle.
I hope you have understand the problem now.
I will tell you more information.
There are some nodes on a graph.
I start always from (0,0).
I should go to the node with the biggest x and then to return to (0,0) in the shortest cycle. In this path i have to pass from all the nodes.
As i go to the node with biggest x i should always go toward x axes (xprevious<xnext) and as i return (xnext<xprevious).
I have to find the shortest path to make this cycle.I hope you have understand the problem now.
Draw it out on paper. Your restrictions give you an idea of what your edges can be. There are a few ways one could interpret what you wrote as far as the rules go. You have at least one incorrect statement in your description:
As i go to the node with biggest x i should always go toward x axes (xprevious<xnext) and as i return (xnext<xprevious).
The x-axis is the horizontal axis. The distance from a node to the x-axis is based on the y value, not the x value. I assume you mean y-axis rather than x-axis, but if xprevious < xnext, you are moving AWAY from the y-axis, not TOWARD it with each step (assuming all x values are positive, which you haven't actually stated).
Keep in mind that the only thing we know about your assignment is what you tell us, so your language must be as precise as possible. Start by drawing a bunch of small graphs on paper (start with the trivial 2-node graph, then 3, then 4, then 5, then 6) and figuring out the correct answer. A directed trial-and-error campaign will clarify the problem, clarify the issues involved, and suggest an algorithm.
You have at least one incorrect statement in your description:
The x-axis is the horizontal axis. The distance from a node to the x-axis is based on the y value, not the x value. I assume you mean y-axis rather than x-axis, but if xprevious < xnext, you are moving AWAY from the y-axis, not TOWARD it with each step (assuming all x values are positive, which you haven't actually stated).
I meant that i should move along x-axis. So xprevious < xnext is correct.
I will try it, although i search for a solution long time.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.