Find the least cost path between two nodes in a graph.

[mir12]

Hi it would be great help if anybody can guide me through this Question

Problem: Find the least cost path between two nodes in a graph.

The input for building the node graph for the problem will be in the format as below.

Enter Nodes and Weight (Q to terminate):

: AB 2

: AC 5

: AD 10

: AE 11

: BC 12

: BD 14

: CE 16

[darkagn]

Hi mir12 and welcome to DaniWeb,

We have pretty strict rules here about doing other people's homework for them (we won't!!) So you need to show us what you've done, and ask some specific questions about your problem.

[bugmenot]

http://en.wikipedia.org/wiki/Shortest_path_problem

[Duoas]

Before you read that link, you should be aware that if you are doing this for an algorithms class the professor expects you to figure this out on your own. It's not that hard. Oh, and he will know if you use one of the algorithms found through that link. (Honestly. Professors can spot that from miles away.)

bugmenot, I'm going to bug you: posting a link to someone else's answer is the same as just giving him the answer yourself. Please don't.

mir12
You'll have to consider several things:

1. How is the graph stored? Does it permit loops? Is the graph directed or not? etc.
2. How do I convert user input into the graph? (What names are the user allowed to use for the nodes? How do I know how many nodes are in the graph when the user is finished with input? What happens if the user enters the same edge twice but with different weights? etc.)

Hint: The way you store the graph will help you solve the problem. What data structure have you studied so far that best represents a graph?

Hint: Use recursion to traverse the graph.

Hope this helps. Let us know if you get stuck.