SimoneRemoli/Dijkstra-s-algorithm_New

Dijkstra’s algorithm is an iterative algorithm that provides us with the shortest path from one particular starting node to all other nodes in the graph.

Dijkstra's algorithm

I created a version of the shortest paths algorithm using the DOT library, which is a filter for drawing directed graphs. The program constructs the graph in real time and associates the weight with each edge.

Simone Remoli

---

Let's look at how it works. 🔍

Tools 🔧

Name	Description
Dot	Filter for drawing directed graphs
Make	A way of automating software building procedure
Semaphore	A way of synch the threads
Parallel Programming	A programming paradigm

Execute 💻

Copy the folder inside your local device and open it with the terminal, the procedure works with any unix-based terminal so if you have a windows-based device use Cygwin and execute the commands from there. To install the DOT Graphviz library necessary for graph visualization, you can type the following command in the terminal:

DOT - DEBIAN / UBUNTU

sudo apt install graphviz

DOT - Fedora, Rocky Linux, Redhat Enterprise Linux, or CentOS

sudo dnf install graphviz

Use git clone to clone a repository from GitHub.com to your local computer.

DOT - Windows 🍷

• graphviz-11.0.0
  • graphviz-11.0.0 (32-bit) ZIP archive [sha256] (contains all tools and libraries)
  • graphviz-11.0.0 (64-bit) ZIP archive [sha256] (contains all tools and libraries)
  • graphviz-11.0.0 (32-bit) EXE installer [sha256]
  • graphviz-11.0.0 (64-bit) EXE installer [sha256]

  Install Cygwin from here.

  
  

  Source execution example 💡

  After you clone into your folder you need to run the make all command.
  Now let's run the code. executable_dijkstra is the executable just created by the make file

  
  As you can see, an adjacency matrix has been generated and the PDF containing the graph design has been created.
  

  The pdf was created successfully. Let's open it.

  
  
  

  Known	Cost
  0	0
  1	6
  2	20
  3	14
  4	2
  5	11
  6	10
  7	11

  As you can see, the software creates a graph where specific weights are associated with the nodes, but it is extremely intelligent and produces the "shortest" path starting from node 0 towards all the other nodes. In particular, the table clearly tells us the "minimum effort" to reach any other node. For example, to reach node 2, starting from node 0, the cost will be 20 because you will have to pass through intermediate nodes which are 4,1,6,10. The path is: 0->4->1->6->10->2. This is the shortest route.

  Example 2

  
  
  ⌛ To reach node 3 starting from node 0 it is clear that you can make a direct "single hop" instead of crossing multiple nodes by lengthening the path. ⌛