Dijkstra's Algorithm?

This is a discussion on Dijkstra's Algorithm? within the C++ Programming forums, part of the General Programming Boards category; Code: void Dijkstra(int s,int t) { vertex *verts = findVertex(grid[s][t]); Heap H; for each(vertex *v in vertexList) { if(v->data == ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    2

    Dijkstra's Algorithm?

    Code:
    void Dijkstra(int s,int t)
        {
            vertex *verts = findVertex(grid[s][t]);
            Heap H;
            for each(vertex *v in vertexList)
            {
                
                if(v->data == verts->data)
                {
                    verts->distance = 0;
                    verts->pred = NULL;
                }
                v->distance = INFINITY;
                v->pred = NULL;
                H.insert(v->data);
            }
            while(H.size() != 0)
            {
                
                vertex *x = findVertex(H.deletemin());
            
                for each(edge *v in x->adjacencyList)
                {
                    
                    if(v->end->visited != true)
                    {    
                    relax(x,v->end);
                    v->end->visited = true;
                    }
                    else
                        break;
                    
                }
                
            }
        }

    is something missing in my dijkstra's, i keep getting an infinite loop. never implemented dijkstra's before so i'm kinda sketchy on how to do it.




    my relax function


    Code:
    void relax(vertex *a, vertex *b)
        {
            
            if(a->distance + weightFrom(a,b) > b->distance)
                {
                    b->distance = a->distance + weightFrom(a,b);
                    b->pred = a;
                }
        
    
    
        }

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    2

    output

    this might be a problem as well.
    when i did a deletemin, some of them are out of order.

    output::


    41
    153
    288
    292
    491
    778
    1842
    1869
    2995
    3035
    3902
    4664
    4827
    5436
    5447
    5705
    6334
    6868
    7711
    8723
    8942
    9040
    9741
    9894
    9961
    11478
    11538
    11942
    12316
    12382
    12859
    14604
    14771
    15141
    15724
    17035
    17421
    17673
    18467
    19264 -
    18716
    19169
    19718
    19912
    21726
    22190
    22648
    23281
    23811
    24464
    25667
    20037-
    26299
    26500
    25547-
    16827-
    26962
    27644
    19895-
    28145
    27529-
    28253
    28703
    29358
    30106
    30333
    31322
    32391
    32662
    32757


    they are marked here. not sure what this means, sorry i'm a beginner at c++.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help me implement Dijkstra's Algorithm
    By iamnew in forum C++ Programming
    Replies: 4
    Last Post: 05-07-2010, 07:02 PM
  2. Dijkstra Algorithm - Not Getting it..
    By johnnyzithers in forum C Programming
    Replies: 1
    Last Post: 10-06-2009, 11:18 PM
  3. Help w/Dijkstra's algorithm
    By dudeomanodude in forum C++ Programming
    Replies: 1
    Last Post: 04-22-2008, 02:26 PM
  4. Dijkstra algorithm problem.
    By apacz in forum C++ Programming
    Replies: 5
    Last Post: 05-28-2005, 04:16 PM
  5. Dijkstra algorithm
    By Micko in forum C++ Programming
    Replies: 5
    Last Post: 04-30-2004, 05:21 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21