help me implement Dijkstra's Algorithm

This is a discussion on help me implement Dijkstra's Algorithm within the C++ Programming forums, part of the General Programming Boards category; The pseudo code of dijkstra's algorithm is Code: function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    help me implement Dijkstra's Algorithm

    The pseudo code of dijkstra's algorithm is

    Code:
         function Dijkstra(Graph, source):
     2      for each vertex v in Graph:           // Initializations
     3          dist[v] := infinity               // Unknown distance function from source to v
     4          previous[v] := undefined          // Previous node in optimal path from source
     5      dist[source] := 0                     // Distance from source to source
     6      Q := the set of all nodes in Graph
            // All nodes in the graph are unoptimized - thus are in Q
     7      while Q is not empty:                 // The main loop
     8          u := vertex in Q with smallest dist[]
     9          if dist[u] = infinity:
    10              break                         // all remaining vertices are inaccessible from source
    11          remove u from Q
    12          for each neighbor v of u:         // where v has not yet been removed from Q.
    13              alt := dist[u] + dist_between(u, v)
    14              if alt < dist[v]:             // Relax (u,v,a)
    15                  dist[v] := alt
    16                  previous[v] := u
    17      return dist[]
    It's from wikipedia.

    I have several clueless area here.

    Firstly i like to know how to implement line numbe 4

    Code:
     previous[v] := undefined          // Previous node in optimal path from source
    what does it mean?

    Please help me.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    Pick a number that you'll be able to recognise as "undefined" later on.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Quote Originally Posted by Salem View Post
    Pick a number that you'll be able to recognise as "undefined" later on.
    I wanted to know what type of data-structure previous is?

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by iamnew View Post
    I wanted to know what type of data-structure previous is?
    Hint: What is the most common sentinal value, and why?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    okay i solved it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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