Experiment 3 Algorithm Issues in Communication Networks-Shortest Path Algorithm Experiment
1. Introduction
-
Single source shortest path problem: Given a weighted directed graph G = (V, E), the weight of each edge is a real number. In addition, a vertex in V is also given, called the source. To calculate the shortest path length from the source to every other vertex. The length here refers to the sum of the rights on all sides of the road. This problem is often called the single-source shortest path problem.
-
Basic idea of basic Dijkstra algorithm:
*1.*When calculating the shortest path in the graph G through Dijkstra, you need to specify a starting point D (that is, starting from the vertex D).
*2.*In addition, introduce two arrays S and U. The function of S is to record the vertices for which the shortest path has been found (and the corresponding shortest path length), while U is to record the vertices for which the shortest path has not yet been found (and the distance from the vertex to the starting point D).
*3.* Initially, there is only the starting point D in the array S; the array U contains vertices other than the starting point D, and the distance from each vertex to the starting point D is recorded in the array U. If the vertex is not adjacent to the starting point D, the distance is infinite.
*4.* Then, find the vertex K with the shortest path from the array U and add it to the array S; at the same time, remove the vertex K from the array U. Next, update the distance from each vertex in the array U to the starting point D.
*5.* Repeat step 4 until all vertices have been traversed.
2. System design requirements
Experimental requirements:
-
Given any weighted connected graph, find the shortest path and the length of the shortest path from the specified starting point to all points, and print out the passed path and the length of the shortest path.
-
Please convert graphics into data and enter via text/manual input.
Print display requirements:
- Request to print all node information:
? For example: Node 1: Chongqing;
? Node 2: **;
?************;
- Request to print all edge information:
? For example: node* node* path length*
- Shortest path information:
?The shortest path length from source node to node*;
? Must pass through node **. . . . . . ;
3. Design ideas and plans
1. Program flow chart design
2. Global variables and structures
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define CITY_NUM 8
#define unconnect INT_MAX // Indicates no connection
int graph[CITY_NUM][CITY_NUM]; // distance between cities
int d[CITY_NUM]; // Distance array, storing the shortest distance from the starting point to each vertex
int p[CITY_NUM]; // Array of predecessor nodes, which stores the predecessor nodes of the shortest path
int S[CITY_NUM]; // Mark visited vertices
char cities[CITY_NUM][20] = {<!-- -->
"Chongqing",
"Beijing",
"Chengdu",
"Shanghai",
"Shenzhen",
"Hangzhou",
"Guangzhou",
"Wuhan"
};
3. Algorithm design
3.1 overall code
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define CITY_NUM 8
#define unconnect INT_MAX // Indicates no connection
int graph[CITY_NUM][CITY_NUM]; // distance between cities
int d[CITY_NUM]; // Distance array, storing the shortest distance from the starting point to each vertex
int p[CITY_NUM]; // Array of predecessor nodes, which stores the predecessor nodes of the shortest path
int S[CITY_NUM]; // Mark visited vertices
char cities[CITY_NUM][20] = {<!-- -->
"Chongqing",
"Beijing",
"Chengdu",
"Shanghai",
"Shenzhen",
"Hangzhou",
"Guangzhou",
"Wuhan"
};
void fileop(void)//Read file structure diagram
{
FILE *fp;
int i, j;
int dis;
int from, to;
if ((fp = fopen("Dijkstra_input.txt", "r")) == NULL)
{
printf("File opening failed");
}
else
{
for (i = 0; i < CITY_NUM; i + + )
{
for (j = 0; j < CITY_NUM; j + + )
{
graph[i][j] = unconnect;
}
}
while (fscanf(fp, "%d %d %d", & amp;from, & amp;to, & amp;dis) == 3)
{
graph[from - 1][to - 1] = dis;
graph[to - 1][from - 1] = dis;
}
fclose(fp);
}
}
//Update distance array and predecessor node array
void Update(int i)
{
for (int j = 0; j < CITY_NUM; j + + )
{
if (!S[j] & amp; & amp; graph[i][j] != unconnect)
{
int newDist = d[i] + graph[i][j];
if (newDist < d[j])
{
d[j] = newDist;
p[j] = i;
}
}
}
}
// Find the vertex with the smallest distance among unvisited vertices
int FindMin()
{
int minDist = INT_MAX;
int minIndex = -1; // Record the vertex with the smallest distance among the unvisited vertices
for (int i = 0; i < CITY_NUM; i + + )
{
if (!S[i] & amp; & amp; d[i] < minDist)
{
minDist = d[i];
minIndex = i;
}
}
return minIndex;
}
void DijkstraAlg(int s)
{
for (int i = 0; i < CITY_NUM; i + + )
{
d[i] = INT_MAX; // Initialize distance to infinity
p[i] = -1; // Initialize the predecessor node to an invalid value
S[i] = 0; // initialization not accessed
}
d[s] = 0;
p[s] = -1;
while (1)
{
int i = FindMin();
if (i == -1)
{
break; // All vertices have been visited
}
S[i] = 1; // Mark vertex i as visited
Update(i);
}
}
void printCities()
{
printf("All node information:\
");
for (int i = 0; i < CITY_NUM; i + + )
{
printf("Node %d: %s;\
", i + 1, cities[i]);
}
printf("\
");
}
void printEdges()
{
printf("Information of all edges:\
");
for (int i = 0; i < CITY_NUM; i + + )
{
for (int j = i + 1; j < CITY_NUM; j + + )
{
if (graph[i][j] != unconnect)
{
printf("The path length from node %d to node %d: %d;\
", i + 1, j + 1, graph[i][j]);
}
}
}
printf("\
");
}
void printShortestPaths(int source)
{
printf("The shortest path length from node %d to each node and the nodes that must pass through:\
", source + 1);
for (int i = 0; i < CITY_NUM; i + + )
{
if (i != source)
{
printf("Shortest distance to node %d: %d\
", i + 1, d[i]);
printf("Required node: ");
int path[CITY_NUM]; // used to store path
int current = i;
int pathLength = 0;
//Traverse the predecessor node array in reverse direction and store the path in the path array
while (current != -1)
{
path[pathLength + + ] = current;
current = p[current];
}
//Print path, from starting point to end point
for (int j = pathLength - 1; j >= 0; j--)
{
printf("%s", cities[path[j]]);
if(j>0)
{
printf(" -> ");
}
}
printf("\
");
}
}
}
int main()
{<!-- -->
int ver1; // Define the starting node
fileop();
printf("Please enter the starting node (1~8):\
");
scanf("%d", & amp;ver1);
if (ver1 < 1 || ver1 > CITY_NUM)
{<!-- -->
printf("Invalid starting node number\
");
return 1;
}
DijkstraAlg(ver1 - 1);
printCities();
printEdges();
printShortestPaths(ver1 - 1);
return 0;
}
3.2 File reading and graph construction
void fileop(void)//Read file structure diagram
{<!-- -->
FILE *fp;
int i, j;
int dis;
int from, to;
if ((fp = fopen("Dijkstra_input.txt", "r")) == NULL)
{<!-- -->
printf("File opening failed");
}
else
{<!-- -->
//Initialize the graph and set the weight between each node to infinity to indicate that it is not connected.
for (i = 0; i < CITY_NUM; i + + )
{<!-- -->
for (j = 0; j < CITY_NUM; j + + )
{<!-- -->
graph[i][j] = unconnect;
}
}
//Read the weights between file nodes and assign them
while (fscanf(fp, "%d %d %d", & amp;from, & amp;to, & amp;dis) == 3)
{<!-- -->
graph[from - 1][to - 1] = dis;
graph[to - 1][from - 1] = dis;
}
fclose(fp);
}
}
3.3 Dijsktra algorithm
The main steps of Dijkstra’s algorithm include initialization, selecting the unvisited node with the smallest distance, marking the visited node, updating the distance and predecessor node array to find the shortest path from the starting point to each node.
//Find the vertex with the smallest distance among unvisited vertices
int FindMin()
{<!-- -->
int minDist = INT_MAX;
int minIndex = -1; // Record the vertex with the smallest distance among the unvisited vertices
for (int i = 0; i < CITY_NUM; i + + )
{<!-- -->
if (!S[i] & amp; & amp; d[i] < minDist)
{<!-- -->
minDist = d[i];
minIndex = i;
}
}
return minIndex;
}
//Update distance array and predecessor node array
void Update(int i)
{<!-- -->
for (int j = 0; j < CITY_NUM; j + + )
{<!-- -->
//If an unvisited node is found
if (!S[j] & amp; & amp; graph[i][j] != unconnect)
{<!-- -->
int newDist = d[i] + graph[i][j];
if (newDist < d[j])
{<!-- -->
d[j] = newDist;
p[j] = i;
}
}
}
}
void DijkstraAlg(int s)
{<!-- -->
for (int i = 0; i < CITY_NUM; i + + )
{<!-- -->
d[i] = INT_MAX; // Initialize distance to infinity
p[i] = -1; // Initialize the predecessor node to an invalid value
S[i] = 0; // initialization not accessed
}
d[s] = 0;
p[s] = -1;
while (1)
{<!-- -->
int i = FindMin();
if (i == -1)//Is there any unvisited node?
{<!-- -->
break; // All vertices have been visited
}
S[i] = 1; // Mark vertex i as visited
Update(i);
}
}
3.4 Print and display information
In the printShortestPaths function, it is necessary to print the necessary paths from the source node to the target node in sequence, because the predecessor node array p stores the shortest path from the source node to each node. The previous node on the path, that is, p[i] stores the index of the previous node on the shortest path from the source node to the node i.
Therefore, it is necessary to traverse the predecessor node array p in reverse order, starting from the target node and tracing back to the source node to construct the complete shortest path.
void printCities()
{<!-- -->
printf("All node information:\
");
for (int i = 0; i < CITY_NUM; i + + )
{<!-- -->
printf("Node %d: %s;\
", i + 1, cities[i]);
}
printf("\
");
}
void printEdges()
{<!-- -->
printf("Information of all edges:\
");
for (int i = 0; i < CITY_NUM; i + + )
{<!-- -->
for (int j = i + 1; j < CITY_NUM; j + + )
{<!-- -->
if (graph[i][j] != unconnect)
{<!-- -->
printf("The path length from node %d to node %d: %d;\
", i + 1, j + 1, graph[i][j]);
}
}
}
printf("\
");
}
void printShortestPaths(int source)
{<!-- -->
printf("The shortest path length from node %d to each node and the nodes that must pass through:\
", source + 1);
for (int i = 0; i < CITY_NUM; i + + )
{<!-- -->
if (i != source)
{<!-- -->
printf("The shortest distance to node %d: %d\
", i + 1, d[i]);
printf("Required node: ");
int path[CITY_NUM]; // used to store path
int current = i;
int pathLength = 0;
//Traverse the predecessor node array in reverse direction and store the path in the path array
while (current != -1)
{<!-- -->
path[pathLength + + ] = current;
current = p[current];
}
//Print path, from starting point to end point
for (int j = pathLength - 1; j >= 0; j--)
{<!-- -->
printf("%s", cities[path[j]]);
if(j>0)
{<!-- -->
printf(" -> ");
}
}
printf("\
");
}
}
}
3.5 Main function
int main()
{<!-- -->
int ver1; // Define the starting node
fileop();
printf("Please enter the starting node (1~8):\
");
scanf("%d", & amp;ver1);
if (ver1 < 1 || ver1 > CITY_NUM)
{<!-- -->
printf("Invalid starting node number\
");
return 1;
}
DijkstraAlg(ver1 - 1);
printCities();
printEdges();
printShortestPaths(ver1 - 1);
return 0;
}
4. Debugging
First test whether reading the file is normal
The printed result is missing the beginning and the end. Find the wrong part in the loop and correct it.
After reading the file correctly, proceed to the next step to build the graph structure.
Successfully constructed the graph structure and continued writing and debugging the Dijsktra algorithm
5. Experience
Break the program into multiple modules or functions, each module is responsible for a different function. This makes the code easier to maintain and understand. In the process of writing a program, you also need to master some basic exception handling, such as file opening failure or invalid input, etc., which improves the robustness of the program.
6. Opinions
Seven. Appendix
Results display
