The "Graph Dijkstra Algorithm" GitHub project is an application allowing to manipulate graphs of different models and origins (or generated by different algorithms). The intended application is the determination of the shortest path (in minutes) to travel from one Paris metro station to another.
Important
The project has been developed exclusively in a professional context, with the specific aim of promoting learning. It is carried out as a project for the University of Paris.
In this project, graphs are implemented in four different ways :
- Edge list :
GrapheLArcs.java - Adjacency Matrix :
GrapheMAdj.java - Adjacency List :
GrapheLAdj.java - Hash Table :
GrapheHHAdj.java
To better understand the concepts of graphs and their different representations or implementations, here is a useful link :
https://algodaily.com/lessons/implementing-graphs-edge-list-adjacency-list-adjacency-matrix [EN]
Remark : The choice of implementing a data structure to represent a graph depends on the specific needs and constraints of the application. Each graph class presented has its advantages and disadvantages in terms of performance and memory usage.
To compile all .java classes, use the following command :
javac -d bin src/main/graphe/**/*.java src/test/java/graphe/**/*.java
This command uses the -d option to specify the destination directory for the .class files, which is bin/ in this case. Paths to .java files are specified using the pattern src/main/graph/**/*.java and src/test/java/graph/**/*.java in order to include all the files present in the respective subdirectories.
To run the Java program, type the following command :
java -cp bin main.graphe.ihm.Main
This command uses the -cp option to specify the classpath to the bin/ directory, which contains the compiled .class files.
For more details about the concept of compilation in Java,, here are some useful links :
Link 1 : https://www.prepbytes.com/blog/java/java-compilation-process [EN]
Link 2 : https://www.baeldung.com/javac [EN]
iut-graph-dijkstra-algorithm/
├─ README.md
├─ LICENSE
├─ performances.txt
├─ Graphs.png
├─ UML_Architecture_Diagram.png
├─ src/
│ ├─ main/
│ │ └─ graphe/
│ │ ├─ algos/
│ │ │ ├─ Dijkstra.java
│ │ │ └─ DijkstraTools.java
│ │ ├─ core/
│ │ │ ├─ Arc.java
│ │ │ ├─ IGraphe.java
│ │ │ └─ IGrapheConst.java
│ │ ├─ exceptions/
│ │ │ ├─ ArcExistantException.java
│ │ │ ├─ ArcInexistantException.java
│ │ │ ├─ ArcValuationNegativeException.java
│ │ │ ├─ EmptySommetException.java
│ │ │ └─ SommetInexistantException.java
│ │ ├─ ihm/
│ │ │ ├─ CheminATrouver.java
│ │ │ ├─ GraphDirectoryImporter.java
│ │ │ ├─ GraphImporter.java
│ │ │ └─ Main.java
│ │ └─ implems/
│ │ ├─ GrapheHHAdj.java
│ │ ├─ GrapheLAdj.java
│ │ ├─ GrapheLArcs.java
│ │ └─ GrapheMAdj.java
│ └─ test/
│ └─ java/
│ └─ graphe/
│ ├─ algos/
│ │ └─ DijkstraTest.java
│ └─ core/
│ └─ IGrapheTest.java
├─ graphs/
│ ├─ barabasi/
│ │ ├─ g-102-1.txt
│ │ ├─ g-1002-1.txt
│ │ ├─ g-10002-1.txt
│ │ ├─ ...
│ │ ├─ g-1000002-1.txt
│ │ ├─ g-1000002-2.txt
│ │ └─ g-1000002-3.txt
│ ├─ full/
│ │ ├─ g-11-1.txt
│ │ ├─ g-101-1.txt
│ │ ├─ g-301-1.txt
│ │ ├─ g-501-1.txt
│ │ └─ g-1001-1.txt
│ └─ orig/
│ ├─ g-10-1.txt
│ ├─ g-10-2.txt
│ ├─ g-10-3.txt
│ ├─ ...
│ ├─ g-100000-4.txt
│ ├─ g-1000000-1.txt
│ └─ g-1000000-2.txt
└─ answers/
├─ barabasi/
│ ├─ r-102-1.txt
│ ├─ r-1002-1.txt
│ ├─ r-10002-1.txt
│ ├─ ...
│ ├─ r-1000002-1.txt
│ ├─ r-1000002-2.txt
│ └─ r-1000002-3.txt
├─ full/
│ ├─ r-11-1.txt
│ ├─ r-101-1.txt
│ ├─ r-301-1.txt
│ ├─ r-501-1.txt
│ └─ r-1001-1.txt
└─ orig/
├─ r-10-1.txt
├─ r-10-2.txt
├─ r-10-3.txt
├─ ...
├─ r-100000-4.txt
├─ r-1000000-1.txt
└─ r-1000000-2.txt
Named performances.txt, the file contains the performance metrics for the different graph types (orig, barabasi and full).
Named UML_Architecture_Diagram.png, the image contains the project's architecture diagram.
Named graphs and answers, the folders contain the initial graphs on one side and the shortest path for each graph of each size.
Created by @Corentin-Lcs. Feel free to contact me !
Distributed under the GNU GPLv3 license. See LICENSE for more information.