Shortest path algorithm – C++ implementation of dijsktra and floyd

For the definition of the graph in the following algorithm, please see this article: (56 messages) Minimum Spanning Tree Algorithm – C++ Implementation of Kruskal and Prim Algorithms_Aaaverage JOE’s Blog-CSDN Bloghttps://blog.csdn.net/m0_73961454/article/details/130814908

Implementation of Dijsktra algorithm: This is a single-source path algorithm, that is, it can only find the shortest path from one point to other points

Node* getMindistanceAndUnselectedNode(unordered_map<Node*,int> & amp; distanceMap,set<Node*> & amp; selectedNode) {
int mindistance = INT_MAX;
Node* minNode = NULL;
for (pair<Node*,int> it : distanceMap) {
Node* node = it. first;
int distance = it. second;
if (distance < mindistance & amp; & amp; selectedNode.count(node) == 0) {
mind distance = distance;
minNode = node;
}
}
return minNode;
}
unordered_map<Node*, int> Dijsktra(Node* head) {
unordered_map<Node*, int> distanceMap;
if (head == NULL) {
return distanceMap;
}
distanceMap[head] = 0;
set<Node*> selectedNode;
Node* minNode = getMindistanceAndUnselectedNode(distanceMap, selectedNode);
while (minNode != NULL) {
int distance = distanceMap[minNode];
for (Edge* edge : minNode->edges) {
Node* to = edge->to;
if (distanceMap.count(to) == 0) {
distanceMap[to] = distance + edge->weight;
}
distanceMap[to] = fminf(distanceMap[to], distance + edge->weight);
}
selectedNode.insert(minNode);
minNode = getMindistanceAndUnselectedNode(distanceMap, selectedNode);
}
return distanceMap;
}

The optimized version of Dijsktra (using the enhanced heap, that is, adding an index to the heap):

unordered_map<Node*,int> dijsktraByheap(Node* node,int size) {
unordered_map<Node*, int> result;
if (node == NULL) {
return result;
}
Nodeheap heap(size);
heap.AddorUpdateorIgnore(node, 0);
while (!heap. isEmpty()) {
NodeRecord* temp = heap. pop();
int distance = temp->distance;
node = temp->node;
for (Edge* edge : node->edges) {
Node* to = edge->to;
heap.AddorUpdateorIgnore(to, edge->weight + distance);
}
result[node] = distance;
}
return result;
}

//heap optimization of dijsktra algorithm
class NodeRecord {
public:
int distance;
Node* node;
NodeRecord(Node* n,int v) :distance(v), node(n) {}
};
class Nodeheap {
private:
Node** arr;//Array storing Node* elements
unordered_map<Node*, int> distanceMap;
unordered_map<Node*, int> indexMap;//mark the subscript of the node in the array, if not in the array, it is -1
int heapsize;
public:
Nodeheap(int s) {
heapsize = 0;
arr = new Node*[s]();
}
void swap(int index1, int index2) {
// swap elements in the array
Node* temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
//Exchange the index in the index table
indexMap[arr[index1]] = index2;
indexMap[arr[index2]] = index1;
}
//Compare the index position with its child, and exchange it if the distance is large
void heapify(int index) {
int left = index * 2 + 1;
while (left < heapsize) {
int min = left + 1 < heapsize & amp; & amp; distanceMap[arr[left]] < distanceMap[arr[left + 1]] ? left : left + 1;
min = distanceMap[arr[index]] < distanceMap[arr[min]] ? index : min;
if (index == min) {
return;
}
swap(index, min);
index = min;
left = index * 2 + 1;
}
}
//Compare the index position with its parent, and exchange if the distance is large
void heapInsert(int index) {
while (distanceMap[arr[index]] < distanceMap[arr[(index - 1) / 2]]) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
//If it is not in the heap, add it directly; if it is in the heap, it needs to be compared, if it is smaller, update it; otherwise, do nothing
void AddorUpdateorIgnore(Node* node, int distance) {
if (!isEntered(node)) {
arr[heapsize] = node;
distanceMap[node] = distance;
indexMap[node] = heapsize;
heapInsert(heapsize++);
return;
}
if (inheap(node) & amp; & amp; distanceMap[node] > distance) {
distanceMap[node] = distance;
heapify(indexMap[node]);
}
}
//Pop up the minimum distance at this time, the operation of popping up is equivalent to adding this node to selectedNodes and selecting minNode
NodeRecord* pop() {
NodeRecord* res = new NodeRecord(arr[0], distanceMap[arr[0]]);
swap(0, --heapsize);
indexMap[arr[heapsize]] = -1;
distanceMap.erase(arr[heapsize]);
heapify(0);
return res;
}

//Judge whether this node has entered the heap, in order to use it for the Add function (if it has not entered, add it directly)
bool isEntered(Node* node) {
return indexMap.count(node) != 0;
}

//Judge whether this node is in the heap, only in the heap is it possible to update
bool inheap(Node* node) {
return isEntered(node) & amp; & amp; indexMap[node] != -1;
}
bool isEmpty() {
return heapsize == 0;
}
};

Multi-source shortest path algorithm: Find the shortest path from each vertex in the graph to other vertices. Of course, we can call multiple Dijsktra algorithms, but the efficiency is too low, so there is the floyd algorithm

Implementation of Floyd’s algorithm:

void floyd(int(*G)[MAX_VEX], int(*A)[MAX_VEX], int(*path)[MAX_VEX]) {
if (G == NULL || A == NULL || path == NULL) {
return;
}
for (int i = 0; i < MAX_VEX; i ++ ) {
for (int j = 0; j < MAX_VEX; j++ ) {
A[i][j] = G[i][j];
path[i][j] = -1;
}
}
for (int v = 0; v < MAX_VEX; v ++ ) {
for (int i = 0; i < MAX_VEX; i ++ ) {
for (int j = 0; j < MAX_VEX; j++ ) {
if (A[i][j] > A[i][v] + A[v][j]) {
A[i][j] = A[i][v] + A[v][j];
path[i][j] = v;
}
}
}
}
}

Let’s talk about the function parameters here:

This is a pointer to a two-dimensional array, because the essence of an array is a continuous space in memory. The two-dimensional array arr is composed of one-dimensional arrays. For example, arr[0] = *(arr + 0), arr is the base address, so that the 0th one-dimensional array in the two-dimensional array is obtained

arr[0][1] = *(*(arr + 0) + 1)

Therefore, the name of the array is the base address for opening up a continuous space in the memory, and the address is the pointer. Adding the number will add the corresponding memory number by the compiler according to its type, such as int* p;p[1] = *( p + 1), where 4 bytes of int type are added, and a memory unit is a byte

How to get the shortest path between given nodes:

int GetMindistanceByFloyd(int(*A)[MAX_VEX], int(*path)[MAX_VEX], int i, int j) {
if (path[i][j] == -1) {
return A[i][j];
}
int v = path[i][j];
int val1 = GetMindistanceByFloyd(A, path, i, v);
int val2 = GetMindistanceByFloyd(A, path, v, j);
return val1 + val2;
}