Applications of Graphs 2.0—–Shortest Path Problem (Dijkstra and Floyd Algorithm)

Table of Contents

Preface

shortest path

Dijkstra’s algorithm

1. Algorithm steps

2. Code implementation

3. Algorithm analysis

Floyd’s algorithm

1. Algorithm steps

2. Code implementation

3. Algorithm analysis

Foreword

Today we continue to study the application of graphs, the shortest path problem. The so-called shortest path is to find the shortest path from one point to another point. Then here we can implement it through the Dijkstra algorithm. The idea of this algorithm is rather convoluted, but I will explain it in detail below.

Data Structure–Quartet of Graph Applications
Minimum Spanning Tree Problem: Application of Graphs 1.0—–Minimum Spanning Tree Problem-CSDN Blog
Shortest path problem (Djkstra’s algorithm): Application of graphs 2.0—–Shortest path problem (Dijkstra and Floyd’s algorithm)-CSDN blog

Topological Sorting: Graph Application 3.0—–Topological Sorting-CSDN Blog
Critical Path Algorithm: Graph Application 4.0—–Critical Path (AOE Network)-CSDN Blog

Shortest path

Typical use: Transportation network issues-Is there a road connection from point A to point B?

When there are multiple paths, which path is the shortest?

The transportation network is represented by directed network:

Vertex – indicates location;

Arc – indicates that two locations are connected by a road;

The weight on the arc – represents the distance between two locations, transportation costs or time spent on the way, etc.

How to minimize the transportation time or save the freight from one location to another? This is a problem of finding the shortest path between two locations.

Problem abstraction: Among the multiple paths from point A (source point) to point B (end point) in a directed network, find a path with the smallest sum of edge weights, that is, the shortest path.

The shortest path is different from the minimum spanning tree. The path does not necessarily contain n vertices or n-1 edges

(1)

(2)

Two common shortest path problems:

Single source shortest path using Dijkstra’s algorithm

The shortest path between all vertices – using Floyd’s algorithm

Below I will introduce these two algorithms respectively.

Dijkstra’s algorithm

Dijkstra’s algorithm is an algorithm discovered by Dutch computer scientist Edsger Wybe Dijkstra in 1956. Dijkstra’s algorithm uses a method similar to breadth-first search to solve the single-source shortest path of a weighted graph. Question. The original version of Dijkstra’s algorithm is only suitable for finding the shortest path between two vertices. Later, more common variants fix a vertex as the source node and then find the shortest path from that vertex to all other nodes in the graph, producing a shortest path. Tree. This algorithm takes out the smallest distance among unvisited nodes each time, and uses this node to update the distances of other nodes. It should be noted that most Dijkstra’s algorithms cannot effectively handle graphs with negative weight edges.

1. Algorithm steps

Initialization: First find the direct path (vo, vk) from the source point vo to each end point v, that is, the path reached through an arc.

Selection: Find the shortest path (vo,u) from these paths

Update: Then make appropriate adjustments to the remaining paths:

If there is an arc (u,vk) in the graph, and (v0,u) + (u,vk)<(v0,vk),

Then replace (v0, vk) with the path (v0, u; vk).

Among the adjusted paths, find the path with the shortest length, and so on.

Legend:

2. Code implementation

Code ideas:

Corresponding to this algorithm, how do we write this code?

First, three arrays are needed, namely path, dis_min, and comp. The functions of these three arrays are to record each position traversed by the starting point, record the nearest distance from the starting point to other vertices, and the distance to other vertices in the set U (set U Initialized as the starting point, each time a point is traversed, the point is added to the set U)

Then find the closest distance from the starting point to other vertices in the set U, return the position and path length of this vertex, and store them in path and dis_min respectively. Then add the new vertex to the set U and update the comp array.

Correlation structure of adjacency matrix:

#define Maxint 32767
#define Maxnum 100//Maximum number of vertices


//type of data
typedef struct d {
char id[10];
//…
}
ElemType;
//Adjacency array of graph
typedef struct graph {
ElemType vexs[Maxnum];//Graph data
int matrix[Maxnum][Maxnum];//two-dimensional array
int vexnum;//points
int arcnum;//Number of sides
}Graph;

Dijkstra algorithm code:

//Structure from the nearest vertex:
typedef struct node {
int index;//subscript
int dis;//distance to this vertex
}Nearest;
//comp finds the nearest vertex
Nearest find_min(int* comp,int n) {
Nearest loca_min;
//Initialize, find the first data in comp that is not -1
for (int j = 0; j < n; j + + ) {
if (comp[j] != -1) {
loca_min.dis = comp[j];
loca_min.index = j;
break;
}
}
//Find the vertex of the current minimum value of comp
for (int i = 0; i < n; i + + ) {
if (comp[i]!=-1) {
if (loca_min.dis > comp[i]) {
loca_min.index = i;
loca_min.dis = comp[i];
}
}
}
return loca_min;
}

//Dijkstra algorithm
void Dijkstra(Graph G, char* start_id) {
printf("(Dijkstra algorithm) shortest path from starting point to other vertices:\\
");

int* dis_min = (int*)malloc(sizeof(int) * G.vexnum);//Record the shortest path from the starting point to other vertices
int* path = (int*)malloc(sizeof(int) * G.vexnum);//Record the sequential process of traversal
int* comp= (int*)malloc(sizeof(int) * G.vexnum);//The distance between the starting point and other vertices in the current set U

\t//initial position
int start = Locate_vex(G, start_id);
//Preliminary processing
for (int i = 0; i < G.vexnum; i + + ) {
path[i] = -1;
comp[i] = G.matrix[start][i];
}
int count = 0;
path[count] = start;
dis_min[count] = 0;
comp[start] = -1;//marked as -1, indicating that this point is already in the set U
count + + ;

//Subsequent processing
for (int i = 0; i < G.vexnum-1; i + + ) {
Nearest loca_min= find_min(comp,G.vexnum);

int k= loca_min.index;
int new_mindis = loca_min.dis;
//Put the latest new point found and relevant data into path and dis_min
path[count] = loca_min.index;
dis_min[count] = loca_min.dis;
count + + ;
comp[k] = -1;//Mark this vertex as having been added to the set U

//Output, the nearest distance result from the starting point to this point
printf("%s->%s %d\\
", G.vexs[start].id,G.vexs[k].id,new_mindis);
\t\t
//comp array update comparison
for (int j = 0; j < G.vexnum; j + + ) {
if (comp[j]!=-1) {
if (comp[j] > G.matrix[k][j] + new_mindis) {
comp[j] = G.matrix[k][j] + new_mindis;
}
}
}
}

//Output path path
for (int i = 0; i < G.vexnum; i + + ) {
printf("%s ", G.vexs[path[i]].id);
}

//Release space
free(dis_min);
free(path);
free(comp);
dis_min = path = comp = NULL;
}

Enter the data of the relevant edges and points of this graph:

Test results:

3. Algorithm Analysis

Suppose the graph has n vertices and e edges

Time complexity: O(n^2)

Space complexity:O(n)

Floyd algorithm

Dijkstra is suitable for non-negative weight graphs, and can only find the shortest path from the source point to any node in the network at a time, while Floyd’s algorithm is more widely used and can find the shortest path between any two points in the network, and Floyd’s algorithm is more widely used. Ide’s algorithm is suitable for negative weight graphs. This article will introduce Freud’s algorithm in the form of graphs and tables!

1. Algorithm steps

Algorithmic Thought

Test vertices one by one

In all possible paths from vi to vj

Choose a path with the shortest length

Steps to find the shortest path:

Initially, set an n-order square matrix and set its diagonal element to 0. If there is an arc , the corresponding element is the weight; otherwise, it is oo.

Gradually try to add intermediate vertices to the original direct path. If the path becomes shorter after adding intermediate vertices, modify it; otherwise, maintain the original value. All vertices have been tested and the algorithm ends.

The process is as follows:

2. Code implementation

//Floyd algorithm
void Floyd(Graph G) {
Graph V = G;//Graph V is used as a modified graph to store each vertex and find the closest distance to other vertices.
for (int i = 0; i < G.vexnum; i + + ) {
int add = i;//Add the add-th vertex to it
for (int j = 0; j < G.vexnum; j + + ) {//Starting vertex
for (int k = 0; k < G.vexnum; k + + ) {//Target vertex
if (V.matrix[j][k] > V.matrix[j][add] + G.matrix[add][k])
V.matrix[j][k] = V.matrix[j][add] + G.matrix[add][k];
}
}
}
//Print the matrix of graph V
print_matrix(V);

printf("\\
Floyd algorithm results are as follows:\\
");
for (int i = 0; i < V.vexnum; i + + ) {
for (int j = i; j < V.vexnum; j + + ) {
printf("%s->%s min_distance:%d\\
", V.vexs[i].id, V.vexs[j].id,V.matrix[i][j]);
}
}
}

3. Algorithm analysis

Suppose the current graph has n vertices and you have n edges

Time complexity: O(n^3)

The above is the entire content of this issue. If you like it, please give it a like!

Share a wallpaper:

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57035 people are learning the system