#Before I started to write blog, I was very grateful to the algorithm teacher I met in my junior year. I was ignorant in my freshman year and sophomore year. I felt that I wasted a lot of time. I met better people and teachers in my junior year and moved to a better campus. I knew that, in fact, there was only one enemy of the subject, that is myself.
A hundred years of poisonous chicken soup, no more nonsense, because I still have a lot of homework not written
*Compiler vs2013
*Language C++
(ps: use adjacency matrix to store digraphs)
An example of solving the shortest path

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <map>
#define random(a,b) (rand()%(b-a+1)+a)
//Functions used to generate random numbers
using namespace std;
//create a paragraph with 100 nodes and 3000 edges
typedef struct Node{
    int vertex;
    int weight;
    Node * next;
};
static int MAX_SIZE = 10000000;
static int VC = 100;
struct Node * HeadNode;
map<int, Node*> Heads;
map<int, int> store_stack;
int vertex_size=0;
bool marked[101];
int dis[101];
int previous[101];
//All storage starts at 1
//initialization count vertex head pointer and store it in the Heads
//Here, count refers to the number of nodes to be randomly generated
void initLinks(int count){
    for (int i = 1; i <= count; i++){
        Node* head = new Node;
        head->vertex = i;
        head->weight = 0;
        head->next = NULL;
        Heads[i] = head;
    }
    vertex_size = count;
}

//create a new node and insert into the link of corresponding vertex node link
void insertNode(int vertex1,int vertex2,int weight){
    Node *node = new Node;
    node->vertex = vertex2;
    node->weight = weight;
    node->next = NULL;
    Node * head = Heads[vertex1];
    while (head->next != NULL){
        head = head->next;
    }
    head->next = node;
}
void showNodeItems(Node * head){
    while (head != NULL){
        cout << "(";
        cout << head->vertex<<"*";
        cout << head->weight <<")";
        head = head->next;
    }
    cout << " " << endl;
}
void  showLinksNode(map<int, Node*> Heads){
    //Using the iterator of map for iterative operation
    map<int, Node* >::iterator it;

    for (it = Heads.begin(); it != Heads.end(); it++){
        //first is key
        //second is value
        showNodeItems(it->second);
    }
}
//generate count vertexs  in the form of (beginvertex,endinvertex,weight)
//both vertex range from 1 - 100 and weight range from 10-90
//rand()%num produces a random integer from 0 to num-1
//Generate a weight ed directed edge from beginvertex to endvertex
void genPairs(int count){
    srand((unsigned)time(NULL));
    //Random number seed
    int counter = 0;
    while (counter<count){
        int vertex1 = random(1, 100);
        int vertex2 = random(1, 100);
        int weight = random(10, 90);
        if (vertex1 == vertex2){
            continue;
        }
        counter++;
        insertNode(vertex1, vertex2, weight);
    }
    //showLinksNode(Heads);
}
//Select any point as the source point S, and find the distance from the point to each vertex
//Dijkstra algorithm shortest path
//a marked array, distance array,previous array
//The implementation idea is to continuously add the current shortest directed path before all vertices are not marked, then update the distance and add the precursor information

int getDistance(int from, int to){
    if (from <= 0 || to <= 0){
        cout << "parameters error" << endl;
        return -1;
    }
    if (from == to){
        return 0;
    }
    Node * head = Heads[from];
    int temp = MAX_SIZE;
    while (head!= NULL){
        int vertex_to = head->vertex;
        if (vertex_to == to&&head->weight<MAX_SIZE){
            temp = head->weight;
        }
        head = head->next;
    }
    return temp;
}
//Determine whether all points have been traversed
int allMarked(){
    for (int i = 1; i <= vertex_size; i++){
        if (marked[i] == 0)
            return 0;
    }
    return 1;
}
void ShowResult(int vertex){
    cout << "------------      from" << vertex << "The distance to each point is as follows-----------          " << endl;
    cout << "-------------The first row of data is the distance from the source point to each point------------" << endl;
    for (int i = 1; i <= vertex_size; i++){
        cout << dis[i] << "   ";

    }
    cout << endl;
    cout << "-------------The second row of data is the precursor of each point----------------" << endl;
    for (int i = 1; i <= vertex_size; i++){
        cout << previous[i]<< "   ";
    }
    cout << "Thank you for using." << endl;

}
void dijkstra(int vertex){
    //Cycle stop indication
    int currentNode = vertex;
    //Initializing the set of marked,distance, and previous variables
    for (int i = 1; i <= vertex_size; i++){
        if (i == currentNode){
            marked[i] = 1;
            dis[i] = 0;
            previous[i] = -1;
        }
        else{
            marked[i] == 0;//Undiscovered points
            dis[i] = MAX_SIZE;
            previous[i] = -1;
        }
    }

    //This part has just been written in the loop, resulting in.... Unexpected bug
    //currentNode always means that the origin does not need to be updated,
    //Initial value should be assigned when selecting the next point
    for (int i = 1; i <= vertex_size; i++){
        if (marked[i] == 0){
            int shorter = getDistance(currentNode, i);
            if (shorter < MAX_SIZE){
                dis[i] = shorter;//The least temporary edge
                previous[i] = currentNode;
            }
        }
    }

    //Start pathfinding until all vertices are marked
    while (!allMarked()){       
        int minvetex = MAX_SIZE;
        int nextvertex = 0;
        //seek for the minist vertex as the next source vertex and update the distance array
        for (int j = 1; j <= vertex_size; j++){
            if (!marked[j]){
                if (dis[j] < minvetex){
                    minvetex = dis[j];
                    nextvertex = j;
                }
            }
        }

        marked[nextvertex] = 1;
        //Cout < < No. < nextvertex < < selected as newly added vertex < < endl;

        //update the array
        for (int k = 1; k <= vertex_size; k++){
            if (marked[k] == 0){
                int tem = getDistance(nextvertex, k)+dis[nextvertex];
                if (tem<dis[k]){
                    previous[k] = nextvertex;
                    //Cout < < will "< dis [k] < update to" < TEM < < endl;
                    dis[k] = tem;
                    //Cout < < update to < K < < vertex distance < endl after adding vertex;

                }
            }
        }
        //currentNode = nextvertex; / / update the source point information to nextvertex

    }

// Cout < < distance of each point is < < endl;
    ShowResult(vertex);
}
//Test case website: https://blog.csdn.net/cjc211322/article/details/24933909
//The test case is the digraph on the above website
void test(){
    insertNode(1, 2, 10);
    insertNode(1, 4, 30);
    insertNode(1, 5, 100);
    insertNode(2, 3, 50);
    insertNode(3, 5, 10);
    insertNode(4, 3, 20);
    insertNode(4, 5, 60);
    vertex_size = 5;
    showLinksNode(Heads);
    dijkstra(1);
}
int main(){
    initLinks(100);
    //genPairs(3000);
    //dijkstra(1);
    //test();
    //Test case, don't forget to change the parameter in initlinks to 5 when testing
    system("pause");
    return 0;
}



  //In conclusion, all algorithms are abstract only by looking at the formula. We need to walk through it to understand this algorithm