This was my final project for Data Structures and Algorithms course at Amirkabir University. It calculates the fair vertex (vertices) in a non-negative weighted undirected graph given some source vertices.
A fair vertex in a graph with a set of source vertices is a vertex with minimum fair score.
Consider the set of source vertices as: {A, B, C, ...}
The fair score for vertex V
is calculated using below formula:
FairScore(V) = |Distance(A, V) - Distance(B, V)| + |Distance(A, V) - Distance(C, V)| + |Distance(B, V) - Distance(C, V)| + ...
Input graph should be of this form:
<number of vertices> <number of edges>
<space-separated list of vertices numbers>
<first vertex of edge> <second vertex of edge> <weight of edge>
...
It only requires fmt.
I implemented a minimal STL-like hash map data structure that I wish to extend. If you are a C++ fan, feel free to contribute.