Does anyone feel like programming?

I've been doing an extensive math assignment but i'm no where near complete. There's a question where we need to develop an algorithm (which isn't even for marks), the analysis and discussion of it are only relevant and worth marks. It's backtracking to find an optimal solution. I'm also under the assumption that this isn't too difficult, or else I wouldn't be asking, i'm just realling pressed for time. Thanks if anybody knows how to write it, or has
already done somehting like this.

problem:
A undirected graph with non-negatively weighted edges. Solve the shortest path from a starting node, to a finishing node. Use backtracking to solve the shortest path (and arrive at an optimal solution).

Code:

---

                                                                    1                          (stating node = 0, ending = 5)
                                                                /  |  \
                                                                /  |  \                                                             
                                                                0---2---3
                                                                |  \  / 
                                                                4    5

Note: any numbers can be used on the above graph, but one example is as good as the next.

---

Don't know your class, but I'd be willing to bet up to a quarter that the reason the algorithm isn't worth any marks is because it's printed in your textbook in a shaded box labeled algorithm 18.4 or the like.

Can you use a common algorythm for this ? i suggest you use DSS or Dijkstra's algorithm.

Ya that could work, i'll probably have to tone it down a bit because it's overly complicated and large. Thanks

You can optimise this algorythems ?

please exaplain how .

This is a simple least cost algorithm like A* (A star). You may want to google A* and see if you can use it. From what it sounds like this is exactly what you need.

It's a matter of checking how many paths current node has and check to see which path is the shortest distance to the end node, go back, take that path, check the paths on the new node and so on..

Well, it is fairly simple. You have no choice but to search all possible paths. Now you have some choices how to search. But there is no optimization there, since your choice effectiveness would depend on the graph.

Now, to find the optimal algorithm you have to first declare what you consider the "cost" of the algorithm. Since it is a math project and not a computer science project you would assume that the cost is only moving from one node to the other. Not memory used, instructions used and whatever else.

In this case again you can't have an optimal solution than searching the whole graph. What you can do though is ASSUME that the graph is completely random.
Thus, every graph of N nodes has the same possibility to exist. Then find what is the most possible biggest route. Lets say it is N/2. Your algorithm would check first paths with length N/2. And you could claim you have the optimal solution. If I was a math professor that is what I would take as optimal, since no other optimization can be made.

Of course it is complicated to find possibilities for N nodes

For 3 nodes for example:
--3 connections
1: 100%
--2 connections
1: 50%
2: 50%
--Overall
possible max length == 1 75%
possible max length == 2 25%
you choose 1 (which is useless of course, but just an example)

It's not true that you have to search all possible paths.
If you have found a solution with a total cost of n and all other partial paths have a cost greater than n, then you can stop immediately.
The "non-negatively weighted edges" part allows you to make that optimisation.

You can't really take advantage of the A* algorithm here because that involves having an estimate of the cost remaining to reach the goal, as well as the total cost travelled along the edges so far. There probably isn't any good way to estimate the remaining cost.
However you can implement a greedy algorithm that tries the shortest-path-so-far first, which is like A* but where the estimated remaining cost is always zero.