Data Structures ( PLEASE HELP ONLY 24hr TO GO)

Hey

ATM im pretty much screwed in my data structures coursework and i really need help on getting start on this Dijkstra Algorithm Coursework

Simple Question
[color=Red]
Dijkstra's algorithm can only be performed on a graph with no negative edge costs. Add a procedure to the Dijkstra program that checks for negative edge lengths in the graph and provides a suitable warning to the user if there are such edges in the graph.[/color]

I'm not sure how to implement a search procedure? do i search through the text file which contain the negative edges? do i search through the adjancey list? or do i search through the graph itself? which is easiet and how the hell do you do it. I show you the example of the text file we have been given. Wondering if anyone could do the code or atleast suggest something!!

# nodes
A: 120,250
B: 250, 320
C: 350,295
D: 300,210
E: 500,200
F: 260,90
G: 360, 100
H: 500,100
[color=Orange]# edges[/color]
A -> B, 22
A -> F, 40
F -> A, 35
A -> D, 30
B -> C, 12
C -> B, -10
C -> E, 26
C -> D, 15
D -> G, 16
G -> F, 5
D -> F, -10
G -> E, 20
G -> H, 14


Your help would be very much appreciated and you will become a LEGEND if u cud help me

Thank you


Comments

  • You will probably want to read the data into an array or in this case, a linked list. I would start by making a data structure (RECORD or OBJECT) that contains points. Also, create another that will handle the paths/edges.

    Then search through your linked list of edges for a negative weight. If encountered, inform the user.


    Phat Nat

    Wikipedia has some good info too:
    http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion