Skip to content

Latest commit

 

History

History
executable file
·
807 lines (545 loc) · 26.7 KB

README.md

File metadata and controls

executable file
·
807 lines (545 loc) · 26.7 KB

Dijkstra's algorithm

/*******************************************************************
                    Dijkstra's algorithm 

    1.  How to use Dijkstra's algorithm in a directed graph

    2.  How to use Dijkstra's algorithm in an undirected graph



                                             COMP9024

 *******************************************************************/

Introduction

We have discussed the format of dot files in COMP9024/Graphs, how to create a directed graph in COMP9024/Graphs/DirectedGraph, and how to create an undirected graph in COMP9024/Graphs/UndirectedGraph.

In this project, we discuss how to determine the shortest path in a graph.

Dijkstra's algorithm is commonly used for finding the shortest path in a graph where the edge weights are non-negative.

To simplify our discussions, we assume the distance from one node to another (edge weight) is a positive integer.

How can we determine the shortest distance from one node to any other node in the graph?

Suppose we start from node 3.

That is, startNodeId is 3.

Initialize the shortest distances to be INFINITY_VALUE ($+\infty$ ).

Initial
  • Basic case

    Update the shortest distance from node 3 to node 3 to be 0.

  • Get the node id (say, u) with the shortest distance from nodes which have not been visited yet.

    Mark node u as visited.

    For one node v,

    if

      (1) node v has not been visited yet 
      (2) node v is a neighbor of node u
      (3) u is reachable from startNodeId (i.e., the shortest distance for u is not INFINITY_VALUE)
      (4) there is a shorter path from startNodeId to v via node u:
    
          startNodeId --> ... -->  u --> v
    
          (i.e., distances[u] + MatrixElement(pGraph, u, v) < distances[v])
    

    then

      Update the distance from startNodeId to v  
    
      distances[v] = distances[u] + MatrixElement(pGraph, u, v) 
    
  • Repeat the previous step until all nodes have been visited.

How can we record the shortest path from one node to any other node in the graph?

Save the node id of the predecessor (i.e., u) of node v when updating distances[v].

distances[v] = distances[u] + MatrixElement(pGraph, u, v)

It will be left as the weekly practical in Tutorial 5 in Week 7

1 How to download Tutorials in CSE VLAB

Open a terminal (Applications -> Terminal Emulator)

$ git clone https://github.com/sheisc/COMP9024.git

$ cd COMP9024/Graphs/Dijkstra

Dijkstra$ 

2 How to start Visual Studio Code to browse/edit/debug a project.

Dijkstra$ code

Two configuration files (Dijkstra/.vscode/launch.json and Dijkstra/.vscode/tasks.json) have been preset.

2.1 Open the project in VS Code

In the window of Visual Studio Code, please click "File" and "Open Folder",

select the folder "COMP9024/Graphs/Dijkstra", then click the "Open" button.

2.2 Build the project in VS Code

click Terminal -> Run Build Task

2.3 Debug the project in VS Code

Open src/main.c, and click to add a breakpoint (say, line 11).

Then, click Run -> Start Debugging

2.4 Directory

├── Makefile             defining set of tasks to be executed (the input file of the 'make' command)
|
├── README.md            introduction to this tutorial
|
├── images               *.dot and *.png files generated by this program
|
├── src                  containing *.c and *.h
|    |
|    ├── Graph.c         containing the code for graphs
|    ├── Graph.h
|    |
|    ├── main.c          main()
|
└── .vscode              containing configuration files for Visual Studio Code
    |
    ├── launch.json      specifying which program to debug and with which debugger,
    |                    used when you click "Run -> Start Debugging"
    |
    └── tasks.json       specifying which task to run (e.g., 'make' or 'make clean')
                         used when you click "Terminal -> Run Build Task" or "Terminal -> Run Task"

Makefile is discussed in COMP9024/C/HowToMake.

3 The main procedure of Dijkstra in a directed graph

3.1 make and ./main

In addition to utilizing VS Code, we can also compile and execute programs directly from the command line interface as follows.

Dijkstra$ make

Dijkstra$ ./main

Shortest path from node 3 to node 0: 4
Shortest path from node 3 to node 1: INF 
Shortest path from node 3 to node 2: 6
Shortest path from node 3 to node 3: 0
Shortest path from node 3 to node 4: 2
Shortest path from node 3 to node 5: 11
Shortest path from node 3 to node 6: 7
Shortest path from node 3 to node 7: 10

3.2 make view

Ensure that you have executed 'make' and './main' before 'make view'.

Observe the procedure of Dijkstra's algorithm (starting from the node 3) via 'make view'

Dijkstra$ make view
find . -name "*.png" | sort | xargs feh &

Click on the window of 'feh' or use your mouse scroll wheel to view images.

Here, feh is an image viewer available in CSE VLAB.

Initial
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8

3.3 More details

Dijkstra$ make

Dijkstra$ ./main

########################### TestDijkstra(directed) ######################


**********  The Adjacency Matrix ************* 
0 0 3 0 4 0 0 0 
0 0 2 0 0 2 0 0 
0 0 0 0 0 5 0 0 
4 0 0 0 2 0 0 0 
0 0 4 0 0 0 5 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 5 0 3 
0 0 0 0 0 0 0 0 

****** Graph Nodes ********
Graph Node 0: 0
Graph Node 1: 1
Graph Node 2: 2
Graph Node 3: 3
Graph Node 4: 4
Graph Node 5: 5
Graph Node 6: 6
Graph Node 7: 7

Dijkstra() starting from node 3:

============================================== Step 1 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:       INF      INF      INF        0      INF      INF      INF      INF
	visited:           0        0        0        0        0        0        0        0

	-----------------------------------------------------------------------------------

Node 3 is selected

Updating distances[0]: 3 --> ... --> 3 --> 0; distance from 3 to 0 is 4

Updating distances[4]: 3 --> ... --> 3 --> 4; distance from 3 to 4 is 2

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF      INF        0        2      INF      INF      INF
	visited:           0        0        0        1        0        0        0        0

	-----------------------------------------------------------------------------------

============================================== Step 2 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF      INF        0        2      INF      INF      INF
	visited:           0        0        0        1        0        0        0        0

	-----------------------------------------------------------------------------------

Node 4 is selected

Updating distances[2]: 3 --> ... --> 4 --> 2; distance from 4 to 2 is 4

Updating distances[6]: 3 --> ... --> 4 --> 6; distance from 4 to 6 is 5

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2      INF        7      INF
	visited:           0        0        0        1        1        0        0        0

	-----------------------------------------------------------------------------------

============================================== Step 3 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2      INF        7      INF
	visited:           0        0        0        1        1        0        0        0

	-----------------------------------------------------------------------------------

Node 0 is selected

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2      INF        7      INF
	visited:           1        0        0        1        1        0        0        0

	-----------------------------------------------------------------------------------

============================================== Step 4 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2      INF        7      INF
	visited:           1        0        0        1        1        0        0        0

	-----------------------------------------------------------------------------------

Node 2 is selected

Updating distances[5]: 3 --> ... --> 2 --> 5; distance from 2 to 5 is 5

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7      INF
	visited:           1        0        1        1        1        0        0        0

	-----------------------------------------------------------------------------------

============================================== Step 5 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7      INF
	visited:           1        0        1        1        1        0        0        0

	-----------------------------------------------------------------------------------

Node 6 is selected

Updating distances[7]: 3 --> ... --> 6 --> 7; distance from 6 to 7 is 3

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7       10
	visited:           1        0        1        1        1        0        1        0

	-----------------------------------------------------------------------------------

============================================== Step 6 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7       10
	visited:           1        0        1        1        1        0        1        0

	-----------------------------------------------------------------------------------

Node 7 is selected

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7       10
	visited:           1        0        1        1        1        0        1        1

	-----------------------------------------------------------------------------------

============================================== Step 7 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7       10
	visited:           1        0        1        1        1        0        1        1

	-----------------------------------------------------------------------------------

Node 5 is selected

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7       10
	visited:           1        0        1        1        1        1        1        1

	-----------------------------------------------------------------------------------

============================================== Step 8 ==============================================

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7       10
	visited:           1        0        1        1        1        1        1        1

	-----------------------------------------------------------------------------------

Node 1 is selected

	-----------------------------------------------------------------------------------
	node id:           0        1        2        3        4        5        6        7
	-----------------------------------------------------------------------------------
	distances:         4      INF        6        0        2       11        7       10
	visited:           1        1        1        1        1        1        1        1

	-----------------------------------------------------------------------------------

Shortest path from node 3 to node 0: 4
Shortest path from node 3 to node 1: INF 
Shortest path from node 3 to node 2: 6
Shortest path from node 3 to node 3: 0
Shortest path from node 3 to node 4: 2
Shortest path from node 3 to node 5: 11
Shortest path from node 3 to node 6: 7
Shortest path from node 3 to node 7: 10

4 The main procedure of Dijkstra in an undirected graph

4.1 make and ./main

In addition to utilizing VS Code, we can also compile and execute programs directly from the command line interface as follows.

Dijkstra$ make

Dijkstra$ ./main

Shortest path from node 3 to node 0: 4
Shortest path from node 3 to node 1: 8
Shortest path from node 3 to node 2: 6
Shortest path from node 3 to node 3: 0
Shortest path from node 3 to node 4: 2
Shortest path from node 3 to node 5: 10
Shortest path from node 3 to node 6: 7
Shortest path from node 3 to node 7: 10

4.2 make view

Ensure that you have executed 'make' and './main' before 'make view'.

Observe the procedure of Dijkstra's algorithm (starting from the node 3) via 'make view'

Dijkstra$ make view
find . -name "*.png" | sort | xargs feh &

Click on the window of 'feh' or use your mouse scroll wheel to view images.

Here, feh is an image viewer available in CSE VLAB.

Initial
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8

5 Data structure

// Storing information of a graph node
struct GraphNode {
    char name[MAX_ID_LEN + 1]; 
};

typedef long AdjMatrixElementTy;

struct Graph{
    /*
        Memory Layout:
                          -----------------------------------------------------------
        pAdjMatrix ---->  Element(0, 0),   Element(0, 1),    ...,       Element(0, n-1),     // each row has n elements
                          Element(1, 0),   Element(1, 1),    ...,       Element(1, n-1),
      
                          .....                            Element(u, v)     ...             // (n * u + v) elements away from Element(0, 0)
      
                          Element(n-1, 0), Element(n-1, 1),  ...,       Element(n-1, n-1)
                          ----------------------------------------------------------- 
                                      Adjacency Matrix on Heap

     */
    AdjMatrixElementTy *pAdjMatrix;
    /*
        Memory Layout
                        ---------------------------
                        pNodes[n-1]
       
       
                        pNodes[1]
        pNodes ----->   pNodes[0]
                       ----------------------------
                        struct GraphNode[n] on Heap
     */
    struct GraphNode *pNodes;
    // number of nodes
    long n;
    // whether it is a directed graph
    int isDirected;
    /*
        Added for Dijkstra       

        Memory Layout
                        ---------------------------
                            distances[n-1]
       
       
                            distances[1]
        distances ----->    distances[0]
                       ----------------------------
                              on Heap
     */
    AdjMatrixElementTy *distances;    
};

// 0 <= u < n,  0 <= v < n
// ELement(u, v) is (n * u + v) elements away from Element(0, 0)
#define  MatrixElement(pGraph, u, v)  (pGraph)->pAdjMatrix[(pGraph)->n * (u) + (v)]

6 Algorithm

#include <limits.h>   // LONG_MAX, INT_MAX

// INFINITY_VALUE must align with the type of AdjMatrixElementTy
#define INFINITY_VALUE  LONG_MAX

// Also see INFINITY_VALUE
typedef long AdjMatrixElementTy;

/*
    Get the node id, 

        (1) not visited yet
        (2) has the minimum distance among the nodes not visited yet
    
 */
static long getNodeIdWithMinDistance(AdjMatrixElementTy *distances, int *visited, long n) {
    AdjMatrixElementTy min = INFINITY_VALUE;
    long minIndex = -1;
    for (long u = 0; u < n; u++) {
        if (!visited[u] && distances[u] <= min) {
            min = distances[u];
            minIndex = u;
        }
    }
    assert(minIndex != -1);
    return minIndex;
}

// Omit the code for visualizing the algorithm
void Dijkstra(struct Graph *pGraph, long startNodeId) {
    assert(IsLegalNodeNum(pGraph, startNodeId));

    AdjMatrixElementTy *distances = pGraph->distances;
    int *visited = (int *) malloc(pGraph->n * sizeof(int));

    assert(visited);

    // Set all the elements in distances[] to be INFINITY_VALUE;
    // Mark all nodes as 'Not Visited Yet'.
    for (long i = 0; i < pGraph->n; i++) {
        distances[i] = INFINITY_VALUE;
        visited[i] = 0;
    }
    // the distance from startNodeId to startNodeId is 0
    distances[startNodeId] = 0;

    // Find the shortest distances
    for (long i = 0; i < pGraph->n; i++) {
        // Get the node id which has the minimum distance among the nodes not visited yet
        long u = getNodeIdWithMinDistance(distances, visited, pGraph->n);
        // set the flag to indicate it has been visited.
        visited[u] = 1;

        // Update the distances of neighbors of node u           
        for (long v = 0; v < pGraph->n; v++) {
            /*
            If the four conditions are true:
                (1) node v has not been visited yet
                (2) there is an edge from u to v (i.e., v is one of u's neighbors)
                (3) distances[u] is not INFINITY_VALUE
                    (i.e., u is reachable from startNodeId)

                (4) there is a shorter path from startNodeId to v (via node u)

                    startNodeId -->  ... --> u --> v
            then
                update distance[v], i.e., the shortest distance from startNodeId to v found so far.
                Note that it might be updated with a shorter distance later.
             */
            if (!visited[v] && MatrixElement(pGraph, u, v) != 0 && distances[u] != INFINITY_VALUE) {
                if (distances[u] + MatrixElement(pGraph, u, v) < distances[v]) {
                    distances[v] = distances[u] + MatrixElement(pGraph, u, v);
                }
            }
        }
    }
    free(visited); 
}

7 How to record the shortest paths from node 3

long *preNodeIds = (long *) malloc(pGraph->n * sizeof(long));

Initial

i 0 1 2 3 4 5 6 7
preNodeIds[i] -1 -1 -1 -1 -1 -1 -1 -1

...

Final

i 0 1 2 3 4 5 6 7
preNodeIds[i] 3 -1 4 3 3 2 4 6

Node preNodeIds[i] is the predecessor of node i in the shortest path when (preNodeIds[i] != -1).

An example

The shortest path from node 3 to node 2:

Searching from node 2.

Predecessor Meaning
preNodeIds[2] is 4 node 4 is the predecessor of node 2
preNodeIds[4] is 3 node 3 is the predecessor of node 4
preNodeIds[3] is 3 Special case; stop searching

We can save the following nodes in a stack.

    2, 4, 3

And then pop the node ids (i.e., reverse the sequence "2, 4, 3")

The shortest path from node 3 to node 2:

    3 --> 4 --> 2

Final

i 0 1 2 3 4 5 6 7
preNodeIds[i] 3 -1 4 3 3 2 4 6

Node preNodeIds[i] is the predecessor of node i in the shortest path.

The above table can be imagined as the following tree.

3 --> 0
3 --> 4
4 --> 2
4 --> 6
2 --> 5
6 --> 7
   
                3
              /    \
             /      \
            0        4
                    /  \
                   /    \
                  2      6
                 /        \
                /          \
               5            7               

Meaning

The shortest path from node 3 to node 0: 4
	3 --> 0
The shortest path from node 3 to node 1: INF 
The shortest path from node 3 to node 2: 6
	3 --> 4 --> 2
The shortest path from node 3 to node 3: 0
	3
The shortest path from node 3 to node 4: 2
	3 --> 4
The shortest path from node 3 to node 5: 11
	3 --> 4 --> 2 --> 5
The shortest path from node 3 to node 6: 7
	3 --> 4 --> 6
The shortest path from node 3 to node 7: 10
	3 --> 4 --> 6 --> 7