Graph_Algo class - Orgamliel7/Ex3- GitHub Wiki

• Graph_Algo implements the interface graph_algorithms

1. What is TSP?

The travelling salesman problem asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?"

2. What is shortest path problem?

The problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. We've decided to use Dijkstra's algorithm to solve it.

3. What is strongly connected problem?

A graph is said to be strongly connected or diconnected if every vertex is reachable from every other vertex.

For more information about our data stracture, you can click the links below:

Dijkstra's algorithm

Travelling salesman problem

strongly connected graph

1. init(graph g) - Init this set of algorithms on the parameter - graph.

2. graph copy() - Compute a deep copy of this graph.

3. init(String file_name) - The method saves the graph to a file.

4. save(String file_name) - he method saves the graph to a file.

5. isConnected() - Returns true if and only if there is a valid path from EVREY node to each other node.

6. shortestPathDist(int src, int dest) - returns the length of the shortest path between src to dest.

7. List<node_data> shortestPath(int src, int dest) - returns the the shortest path between src to dest - as an ordered List of nodes.

8. List<node_data> TSP(List targets) - computes a relatively short path which visit each node in the targets List.