Here below Details description about, how to implement Dijkstra Algorithm :
In this assignment, you will experiment with graphs, and graph algorithm. A social network can be represented as a graph whose vertices represent people and whose edges represent relationships between people. You will implement a program that reads in and analyzes a social network, where the relationship is defined as “knowing” one another. If two people know one another, there will be an undirected edge connecting their corresponding vertices in the graph representation of the social network. Your program will analyze the minimum, maximum and average degree of vertices in the network, the average shortest path length between every pair of persons, the longest shortest path length between two people, and the largest clique in the graph (a set of people who all know each other). Specifically:
1. Your program will take a file name as an argument. The first two lines of the file will contain the number of persons P and number of “knows” relationships R in the file, respectively. The next P lines each start with a consecutive integer (1..P) followed by a space, followed by the person’s name, which is a string of lowercase characters (a-z). The remaining R lines each consist of two integers u and v (1≤u , v≤P ,u≠ v ) separated by a space, which implies that person u and person v know each other. A sample input is
attached below.
2. Your program will represent the information from the file as a graph using either an adjacent list or adjacent matrix representation.
3. Your program will compute and output several statistics about the graph. A sample output is attached below.
Number of vertices
Number of edges
Minimum degree of a vertex – the degree of a vertex is the number of edges connected to the vertex, i.e., the number of people that person knows.
Maximum degree of a vertex
Average degree over all vertices, i.e., the average number of people each person knows.
Average shortest path length between pairs of vertices (You need to apply Dijkstra Algorithm in this step)
Longest shortest path between two vertices
Size and members of the largest complete subgraph (clique) in the social network,
i.e., where everybody knows everybody. If more than one largest group occurs, then output any one of them.
Note: Finding the largest clique in a graph is a NP-complete problem, i.e., may incur an exponential running time in the number of person P in the graph. So, you should implement an efficient version of the clique-finding algorithm, but any version that always finds the maximal clique may take a long time for large graphs.
Have fun!
Sample – Input
8
11
1 bob
2 tom
3 george
4 john
5 mary
6 sally
7 jane
8 allice
1 2
2 3
3 4
4 5
2 6
2 7
3 6
3 7
6 7
6 8
7 8
Sample – Output
Vertices: 8
Edges: 11
Minimum degree: 1
Maximum degree: 4
Average degree: 2.75
Average shortest path length: 1.96
Longest shortest path length: 4
Maximum clique size: 4
Maximum clique members:
2 tom
3 george
6 sally
7 jane
Explanation:
Sample – Input
8
11
1 bob
2 tom
3 george
4 john
5 mary
6 sally
7 jane
8 allice
1 2
2 3
3 4
4 5
2 6
2 7 Edge
3 6
3 7
6 7
6 8
7 8
In Longest Path Matrix, you need to create a matrix by calculating longest path between two nodes like shortest Path matrix.
I hope you can do it itself, after doing it please comments in below sections so we can verify your answer and if anything is needed to modify your code then we can easily added to this.
Commentaires