Today’s Freudian algorithm is very similar to the Dijkstra algorithm, and I’ve put up here a diagram from one of my favorite articles that explains this algorithm, just to make sense of it. I also hope the big man can give more guidance.

Diagram of Freud’s algorithm

即 (King of Thieves)

The title

code

#include <stdio.h>
#include <stdlib.h>


struct graphList
{
    int vexNum;
    int graph[120] [120];
};

int P[120] [120];P (1,3) = 2 indicates that the minimum path from vertex 1 to vertex 3 goes through 2

void createNewGraphList(struct graphList *gList)
{
    int i,j;
    scanf ("%d", &(gList -> vexNum));
    for (i=0; i < gList->vexNum; i++) {for (j = 0; j < gList -> vexNum; j++)
        {
            scanf ("%d", &(gList -> graph[i][j])); }}}void floydAlgorithm(struct graphList *gList)
{
      int v,w,k;
       // Initializes the minimum path matrix of the Floyd algorithm
    for(v = 0; v < gList->vexNum; v++){
        for(w = 0; w < gList->vexNum; w++){ P[v][w] = w; }}// This is the core of Freud's algorithm
    //k is the intermediate point
    for(k=0; k<gList->vexNum; k++) {/ / v as a starting point
         for(v=0; v<gList->vexNum; v++) {/ / w to the end
             for(w=0; w<gList->vexNum; w++) {if(gList->graph[v][w]>gList->graph[v][k]+gList->graph[k][w])
                 {
                     gList->graph[v][w]=gList->graph[v][k]+gList->graph[k][w];// Update the minimum path
                      P[v][w] = P[v][k];// Update the middle vertex of the minimum path
                 }
             }
         }
    }
}

void putOutMinStepNum(struct graphList *gList)
{
    int n;
    int a[10];
    int i, j,k=0;
    scanf ("%d", &n);// The number of outputs
    while (n--)
    {
        scanf ("%d%d", &i, &j);
       a[k]=gList -> graph[i][j];
       k++;
    }
    for(i=0; i<k; i++)printf("%d\n",a[i]);
}

void  putOutMinStep(a)
{
    int i,j;
    scanf("%d %d",&i,&j);
    int k=P[i][j];
    printf("path: %d", i);// Print the starting point
    while(k! =j) {printf("%d\n", k);// Prints the middle point
        k = P[k][j];
    }
    printf("%d",k);// Prints the middle point
}

int main(a)
{
    struct graphList gList;
    createNewGraphList(&gList);
    floydAlgorithm (&gList);
    putOutMinStepNum (&gList);
    //putOutMinStep();
}

Copy the code

Output:To be honest, this Freudian algorithm is much simpler and much better than the Dijkstra algorithm, which is a shame.