Tal tosiano-208846600
Moran shalev-316220938
Building a Directed weighted graph. The project contains 2 algorithms - for finding the shortest route in the graph.
-
Tarjan algorithm which we used to check if the graph is connected or not.
-
A Dijkstra's algorithm uses to find the shortest path in a weighted graph.
-
Interface of a weighted directed graph
-
Interface of algorithms on graphs (weighted tuners).
We built a system that builds a weighted graph by the classes:
represents the set of operations applicable on a node (vertex) in a (directional)
weighted graph.
Every node has data (id-key,location,weight,info,tag) that helps us to representing the graph in In the most accurate way.
represents the set of operations applicable on a directional edge(src,dest,weight) in a (directional) weighted graph.
represents a geo location(x,y,z).represents a Point3D data in the graph.
represents a Directional Weighted Graph with all his elements(Nodes,Edeges)and including many functions that updates his elements.
represents a Directed (positive) Weighted Graph Theory Algorithms and including many algorithms. for the tsp function (Travelling salesman problem) we use the "tarjan" algoritem to solve this problem. for the shortestPathDist function we use the dijkstra's algorithm to solve this problem.
A visual presentation of the graph and the actions we can perform on it.
example of loading G1.json
We load the graph with the "load" button. There are a variety of actions we can perform on the graph, each button performs another action. for example: if we click on the "addNode" button, a vertex will be added to the graph. If we click on the "theShortestDist" buttoמ we will see on the screen the answer to the shortest way from node to another.
| 1000 | 10000 | 100000 | |
|---|---|---|---|
| isConnected | 72 ms | 265 | 3 sec 745 ms |
| shortestpath | 99 ms | 287 ms | 5 sec 443 ms |
| load | 94 ms | 289 ms | 5 sec 538 ms |
| save | 27 ms | 34 ms | 43 ms |
| tsp | 100 ms | 285 ms | 5 sec 426 ms |
