Click here to Skip to main content
11,647,170 members (69,920 online)
Click here to Skip to main content

Dijkstra Algorithm

, 23 Dec 2003 280.6K 17.7K 96
Rate this:
Please Sign up or sign in to vote.
Shortest path (Dijkstra's Algorithm)

Introduction

First of all I must say that I am glad that I can help CodeProject. I tried, and used code from this site and I never took the time to send some of my code. So, the part that it is missing from this site is the Algorithms part, which is important in the programming filed. Let's get into the problem now. The Djkstra algorithm it gives you a headache from the programming point of view. In one step it finds the shortest path to every node in the graph. I will go into the graph background (basics) and then I will present the implementation of this algorithm. This example has also some advanced programming techniques and technologies. I used an ActiveX control (that it is actually the Dijkstra solver) and a container application that use the functions. Also, the lists are made using STL

How to use it

First compile the AnimAlg project and then run the Algorithms project. That's all!

Background (graph theory)

Djikstra's algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem. The somewhat unexpected result that all the paths can be found as easily as one further demonstrates the value of reading the literature on algorithms!

This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph,

G = (V,E) where V is a set of vertices and E is a set of edges. Dijkstra's algorithm keeps two sets of vertices: S the set of vertices whose shortest paths from the source have already been determined and V-S the remaining vertices. The other data structures needed are: d array of best estimates of shortest path to each vertex pi an array of predecessors for each vertex The basic mode of operation is: Initialize d and pi, Set S to empty, While there are still vertices in V-S, Sort the vertices in V-S according to the current best estimate of their distance from the source, Add u, the closest vertex in V-S, to S, Relax all the vertices still in V-S connected to u Relaxation The relaxation process updates the costs of all the vertices, v, connected to a vertex, u, if we could improve the best estimate of the shortest path to v by including (u,v) in the path to v.

Using the code

The container application only use the ActiveX Control. First, must include the control in a Dialog or a FormView, add a variable to it and then use the following code:
void CAlgorithmsView::OnAddNode() 
{
    m_Dijkstra.StartAddNodes();
}

void CAlgorithmsView::OnAddEdge() 
{
    m_Dijkstra.StartAddEdges();
}

void CAlgorithmsView::OnShortestPath() 
{
    CShorthestPath dlg;
    if(dlg.DoModal()==IDOK)    
/* dialog to take 2 longs which means the path*/
    {
        m_Dijkstra.ShortestPath(dlg.m_node1, dlg.m_node2);
    }
}

I will not go too much into the code, I tried to explain there using comments.

Basically, it respects the Graph Theory explained above and the Dijkstra's pseudocode.

Graph Implementation

class CGraph 
{
    public:
    long GetNrNodes();
    CGraph();
    virtual ~CGraph();
    VTYPE_NODE m_nodes; // array of nodes
    VTYPE_EDGE m_edges; // array of edges
    VTYPE_NODE_P d; // array of longs that contain 
          // the shortest path at every step
    VTYPE_NODE_P pi; // array of longs that contain 
          // the predecessor of each node for the shortest path
};
class CNode
{
    public:
    CNode Copy();
    double m_cost; // not used yet
    long m_NodeNr; // node number
    POINT m_p; // graphical point for that node
    CNode();
    virtual ~CNode();
};
class CEdge 
{
    public:
    bool m_red; // used to draw the result 
       // (if an edge it is a part of the shortest path it is drawn in red)
    double m_cost; // the cost of an edge (picked randomly between 0-9)
    long m_secondNode; // the second node number
    long m_firstNode; // the first node number
    POINT m_secondPct; // graphical elements for drawing the edges
    POINT m_firstPct;
    CEdge();
    virtual ~CEdge();
};
// the graph is oriented from the first node to the second node

The Dijkstra's Algorithm (Implementation)

// The Dijkstra's algorithm
STDMETHODIMP CDijkstra::ShortestPath(long node1, long node2)
{
    ReleaseGraph();
    // init d and pi
    InitializeSource(g, g.m_nodes[node1-1]);
    // Set S empty
    VTYPE_NODE S;
    // Put nodes in Q
    VTYPE_NODE Q;
    VTYPE_NODE::iterator kl;
    for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++)
    {
        CNode node = (*kl).Copy();
        Q.push_back(node);
    }
    // Algorithm
    while(Q.size())
    {
        CNode nod = ExtractMin(Q); // the minim value for 
              // the shortest path up to this step
        S.push_back(nod);
        // each vertex v which is a neighbour of u
        VTYPE_NODE::iterator kl;
        for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++)
        {
            if(ExistEdge(nod, (*kl)))
            {
                bool gasit = false;
                VTYPE_NODE::iterator kll;
                for(kll=Q.begin(); kll<Q.end(); kll++)
                {
                    if((*kll).m_NodeNr == (*kl).m_NodeNr)
                    gasit = true;
                }
                if(gasit)
                    Relax(nod, (*kl), GetEdgeVal(nod, (*kl)));
            }
        }
    }
    RefreshDone(node1, node2);
    return S_OK;
}

Links

If you want to see how the algorithm works step by step see the link: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dij-op.html

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

lgciprian
Web Developer
Romania Romania
Education Computer Engineering Faculty 1994-1999
University of Iasi ? Romania
Engineering degree: system and computers
Specialty: programmer analyst
License: (Computer Engineering Faculty) 2000
Master: (Distributed Computing) 2001 - 2002
Final Project: Remote Access. Encrypted file transfer.
Accessing any computer?s desktop through Internet or LAN.
Technologies: COM, ATL, API, SDK, MFC

You may also be interested in...

Comments and Discussions

 
QuestionThank you Pin
LiaoVictor22-Jan-14 15:10
memberLiaoVictor22-Jan-14 15:10 
Generalhelp Pin
hano222222-Mar-10 7:29
memberhano222222-Mar-10 7:29 
Generalplease help me answering..... Pin
annei8-Oct-09 22:29
memberannei8-Oct-09 22:29 
Questionhelp me plsss,,,, Pin
sumario25-Aug-08 20:21
membersumario25-Aug-08 20:21 
GeneralImplementing a Timer Functionality Pin
David James16-Mar-08 5:16
memberDavid James16-Mar-08 5:16 
QuestionQuestion about Dijkstra Algorithm Pin
wongyum11-Mar-08 16:11
memberwongyum11-Mar-08 16:11 
QuestionHow to create Topology for road networks? Pin
dgpdgp7-Aug-07 5:28
memberdgpdgp7-Aug-07 5:28 
GeneralHelp for Dijkstra's graph algo in C# Pin
Asshish4-Jul-07 18:43
memberAsshish4-Jul-07 18:43 
GeneralQuestion Pin
averys24-May-07 3:22
memberaverys24-May-07 3:22 
GeneralVB version of Dijkstra's Algorithm Pin
mergul21-Apr-06 13:00
membermergul21-Apr-06 13:00 
AnswerRe: VB version of Dijkstra's Algorithm Pin
abhijitkolas8-Apr-07 18:57
memberabhijitkolas8-Apr-07 18:57 
Generalcrash Pin
kahnpost@freenet.de30-Jul-05 10:38
memberkahnpost@freenet.de30-Jul-05 10:38 
Generale bun Pin
euacela15-Sep-04 1:46
membereuacela15-Sep-04 1:46 
GeneralNeeded your kind attention Pin
Hammad Raza Kazmi3-Aug-04 21:57
sussHammad Raza Kazmi3-Aug-04 21:57 
You will implement a version of Dijkstra's algorithm with slightly enhanced "book-keeping" so that if there are several minimum distance paths from a source vertex to a destination vertex in a weighted directed graph, you will return the one that has the fewest number of edges.
Recall that Dijkstra's algorithm, as described in the text, allows us to solve the single-source shortest weighted path problem: for a fixed source vertex s, we can calculate the shortest distance dv from s to v for every vertex v in the graph. The algorithm we have discussed also has "book-keeping" to allow us to reconstruct one path whose distance is equal to the minimum distance dv.
Observe, however, that there can be several shortest distance paths from the source vertex s to the destination v. For example, consider the graph consisting of the following set of weighted directed edges, given by triples (from, to, cost):
NYC LosAngeles 400
NYC SanFrancisco 700
NYC SanDiego 600
LosAngeles SanDiego 100
SanDiego SanFrancisco 100
LosAngeles SanFrancisco 200
Imagine, for example, that the edge cost represents the price of a one-way flight from the departure city to the arrival city (for a fairly unusual airline). Then there are two paths from NYC (New York City) to San Francisco with minimum cost of 600:
NYC to LosAngeles to SanDiego to SanFrancisco
NYC to LosAngeles to SanFrancisco
Your program should return the second option, since that journey has only 2 legs rather than 3 legs.
Your assignment is to implement an efficient version of Dijkstra's algorithm with extra book-keeping to allow the minimum distance path with fewest edges to be found. Only a few modifications to the pseudocode given in the text should be required. The main fact to keep in mind is the following (which is what makes the strategy in Dijkstra's algorithm work):
If s = v1 v2 ... vi ... vN = v is a minimum length path from s to v, then for every vertex vi along the path, it must also be true that v1 v2 ... vi is a minimum length path from s to vi.
Suggestion: first complete an efficient implementation of the Dijkstra's algorithm as given in the text, then think about what changes must be made to guarantee that you will also find the minimum cost path with fewest edges. Note that you should not keep track of all minimum length paths to do this.
Technical requirements:
· You must use a priority queue (heap) to allow you to efficiently find the unknown vertex with smallest distance for the main loop of Dijkstra's algorithm. You will need to extend the priority queue for allowing multiple entries for the same vertex and keeping track of whether vertices are known or unknown.
· Read the graph from a text file. You should do at least minimal error checking, such as rejecting negative edges. See the sample input file, flights.txt for an example.
· Allow the user to query source and destination vertices, and print out the minimum path with fewest edges using some kind of clear notation. Here is one example of acceptable output for the graph of cities given above:
· Enter start node:
· >NYC
· Enter destination node:
· >SanFrancisco
· NYC -> LosAngeles -> SanFrancisco


NewYorkCity Boston 100
Chicago NewYorkCity 200
NewYorkCity Hartford 200
Rochester NewYorkCity 200
NewYorkCity Rochester 200
NewYorkCity Seattle 400
Seattle LosAngelese 100
LosAngelese Seattle 150
Seattle Vancouver 100
Vancouver LosAngelese 250
Vancouver SanDiego 300
SanDiego Seattle 200
Chicago SanFrancisco 300
SanFrancisco LosAngelese 200
Chicago LosAngelese 400
Chicago Toronto 350
NewYorkCity Toronto 250
Toronto NewYorkCity 300
NewYorkCity LosAngelese 400
NewYorkCity SanFrancisco 700
NewYorkCity SanDiego 600
LosAngelese SanDiego 100
SanDiego SanFrancisco 100
LosAngelese SanFrancisco 200

GeneralGot Some Problems! Help Please! Pin
RinoMerc4-Jun-04 12:02
memberRinoMerc4-Jun-04 12:02 
GeneralInterestingly, you can often do *much* better than Dijkstra! Pin
Don Clugston4-Jan-04 13:35
memberDon Clugston4-Jan-04 13:35 
GeneralRe: Interestingly, you can often do *much* better than Dijkstra! Pin
kozlowski22-Jan-04 14:15
memberkozlowski22-Jan-04 14:15 
GeneralRe: Interestingly, you can often do *much* better than Dijkstra! Pin
Don Clugston28-Jan-04 18:17
memberDon Clugston28-Jan-04 18:17 
GeneralRe: Interestingly, you can often do *much* better than Dijkstra! Pin
kackermann30-Jul-06 16:37
memberkackermann30-Jul-06 16:37 
GeneralStop condition Pin
kozlowski4-Jan-04 12:10
memberkozlowski4-Jan-04 12:10 
GeneralRe: Stop condition Pin
lgcip6-Jan-04 3:16
memberlgcip6-Jan-04 3:16 
GeneralRe: Stop condition Pin
kozlowski6-Jan-04 13:49
memberkozlowski6-Jan-04 13:49 
GeneralRe: Stop condition Pin
lgcip6-Jan-04 20:28
memberlgcip6-Jan-04 20:28 
GeneralRe: Stop condition Pin
xumepoc14-Sep-11 4:51
memberxumepoc14-Sep-11 4:51 
GeneralJust a comment Pin
Anonymous31-Dec-03 18:41
sussAnonymous31-Dec-03 18:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150804.2 | Last Updated 24 Dec 2003
Article Copyright 2003 by lgciprian
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid