( algorithm ) LAN Shortcut System builds the routing tables for the nodes in a c
ID: 3711107 • Letter: #
Question
( algorithm )
LAN Shortcut System builds the routing tables for the nodes in a computer network, based on shortest-path routing from an any node to all other nodes, where path distance is measured by hop weight, that is, the total weight of edges in a path. The input for this problem is a text file that holds the connectivity information for all the nodes in the network, as in the following example:
241.12.31.14: 241.12.31.15 241.12.31.18 241.12.31.19
Which indicates three network nodes that are connected to 241.12.31.14, that is, three nodes that are one hop away. Edge weight is given by the absolute value of difference between destination and source in last segment of node address. So that, the edge weight between 241.12.31.14 and first node in the example above is 1. The routing table for the node at address A is a set of pairs (B, C), which indicates that, to route a message from A to B, the next node to send to (on the shortest path from A to B) is C. Your program should output the routing table for each node in the network, given an input list of node connectivity lists, each of which is input in the syntax as shown above, one per line.
Requirements:
1. Design two algorithms with two different techniques to solve the given problem
2. Analyze and compare both algorithms
3. Implement the algorithms by using C++/java
4. Test your programs on (same for both algorithms) randomly generated test connected graphs of 50, 100, 150, 200 and 250 vertices
a. For each type of graph generate 20 different random problem sets and report your results in a table (Containing obtained solutions and Computational time)
b. Represent the measurements of the Algorithms in a single table then on a single graph
5. Present this work in a clear and well-organized report
6. Prepare a short video to present your work (10 min maximum)
Documentation:
Write a report with 5 sections. First section includes proposed algorithms pseudocode and their analysis. Second section presents source code of each algorithm. Third section shows screen shots of the output on each tested graph, results’ tables and measurements. Fourth section is the conclusion that summarizes what you do to complete this the project, what the benefits you gain, and your suggestions of other optimization problems can use this algorithm as a solution. In last section, list all references and helps you used in completing this project even tools and libraries.
Explanation / Answer
shortest path algorithm
Dijkstra's calculation is fundamentally the same as Prim's calculation for least spreading over tree. Like Prim's MST, we create a SPT (most limited way tree) with given source as root. We keep up two sets, one set contains vertices incorporated into most brief way tree, other set incorporates vertices not yet incorporated into most limited way tree. At each progression of the calculation, we discover a vertex which is in the other set (arrangement of not yet included) and has least separation from source.
The following are the definite advances utilized as a part of Dijkstra's calculation to locate the most limited way from a solitary source vertex to all different vertices in the given chart.
Calculation
1) Create a set sptSet (most limited way tree set) that monitors vertices incorporated into briefest way tree, i.e., whose base separation from source is ascertained and concluded. At first, this set is unfilled.
2) Assign a separation incentive to all vertices in the info chart. Instate all separation esteems as INFINITE. Relegate remove an incentive as 0 for the source vertex so it is picked first.
3) While sptSet does exclude all vertices
… .a) Pick a vertex u which isn't there in sptSetand has least separation esteem.
… .b) Include u to sptSet.
… .c) Update remove estimation of all contiguous vertices of u. To refresh the separation esteems, repeat through all adjoining vertices. For each contiguous vertex v, if total of separation estimation of u (from source) and weight of edge u-v, is not as much as the separation estimation of v, at that point refresh the separation estimation of v.
Source Code
import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestPath
{
static final int V=9;
int minDistance(int dist[], Boolean sptSet[])
{
int min = Integer.MAX_VALUE, min_index=-1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
void printSolution(int dist[], int n)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i+" tt "+dist[i]);
}
void dijkstra(int graph[][], int src)
{
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
public static void main (String[] args)
{
int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.