从0开始的代码生活（第13天)最小生成树与最短路径

老去光阴速可惊。——出自《采桑子·十年前是尊前客》宋代：欧阳修

• 前言
• 总结

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止，今天我们将通过代码展示其应用

#include 
#include 

#define MAX_DISTANCE 10000


typedef struct Net{
    int** weights;
    int numNodes;
} *NetPtr;


NetPtr initNet(int paraSize, int** paraData) {
    int i, j;
    NetPtr resultPtr = (NetPtr)malloc(sizeof(struct Net));
    resultPtr -> numNodes = paraSize;

    //Two stage space allocation.
    resultPtr->weights = (int**)malloc(paraSize * sizeof(int*));
    for (i = 0; i < paraSize; i ++) {
        resultPtr -> weights[i] = (int*)malloc(paraSize * sizeof(int));
        for (j = 0; j < paraSize; j ++) {
            resultPtr -> weights[i][j] = paraData[i][j];
        }//Of for j
    }//Of for i

    return resultPtr;
}//Of initNet


int dijkstraOrPrim(NetPtr paraPtr, int paraAlgorithm) {
    int i, j, minDistance, tempBestNode, resultCost;
    int source = 0;
    int numNodes = paraPtr->numNodes;
    int *distanceArray = (int*)malloc(numNodes * sizeof(int));
    int *parentArray = (int*)malloc(numNodes * sizeof(int));
    //Essentially boolean
    int *visitedArray = (int*)malloc(numNodes * sizeof(int));

    // Step 1. Initialize. Any node can be the source.
    for (i = 0; i < numNodes; i++) {
        distanceArray[i] = paraPtr->weights[source][i];
        parentArray[i] = source;
        visitedArray[i] = 0;
    } // Of for i
    distanceArray[source] = 0;
    parentArray[source] = -1;
    visitedArray[source] = 1;

    // Step 2. Main loops.
    tempBestNode = -1;
    for (i = 0; i < numNodes - 1; i++) {
        // Step 2.1 Find out the best next node.
        minDistance = MAX_DISTANCE;
        for (j = 0; j < numNodes; j++) {
            // This node is visited.
            if (visitedArray[j]) {
                continue;
            } // Of if

            if (minDistance > distanceArray[j]) {
                minDistance = distanceArray[j];
                tempBestNode = j;
            } // Of if
        } // Of for j

        visitedArray[tempBestNode] = 1;

        // Step 2.2 Prepare for the next round.
        for (j = 0; j < numNodes ; j++) {
            // This node is visited.
            if (visitedArray[j]) {
                continue;
            } // Of if

            // This node cannot be reached.
            if (paraPtr->weights[tempBestNode][j] >= MAX_DISTANCE) {
                continue;
            } // Of if

            // Attention: the difference between Dijkstra and Prim algorithms.
            if (paraAlgorithm == 0) {
                if (distanceArray[j] > distanceArray[tempBestNode] + paraPtr->weights[tempBestNode][j]) {
                    // Change the distance.
                    distanceArray[j] = distanceArray[tempBestNode] + paraPtr->weights[tempBestNode][j];
                    // Change the parent.
                    parentArray[j] = tempBestNode;
                } // Of if
            } else {
                if (distanceArray[j] > paraPtr->weights[tempBestNode][j]) {
                    // Change the distance.
                    distanceArray[j] = paraPtr->weights[tempBestNode][j];
                    // Change the parent.
                    parentArray[j] = tempBestNode;
                } // Of if
            }//Of if
        } // Of for j
    } // Of for i

    printf("the parent of each node: ");
    for (i = 0; i < numNodes; i++) {
        printf("%d, ", parentArray[i]);
    } // Of for i

    if (paraAlgorithm == 0) {
        printf("From node 0, path length to all nodes are: ");
        for (i = 0; i < numNodes; i++) {
            printf("%d (%d), ", i, distanceArray[i]);
        } // Of for i
    } else {
        resultCost = 0;//
        for (i = 0; i < numNodes; i++) {
            resultCost += distanceArray[i];
            printf("cost of node %d is %d, total = %drn", i, distanceArray[i], resultCost);
        } // Of for i
        printf("Finally, the total cost is %d.rn ", resultCost);
    }//Of if

    // Step 3. Output for debug.
    printf("rn");

    return resultCost;
}// Of dijkstraOrPrim


NetPtr constructSampleNet() {
    int i, j;
    int myGraph[6][6] = {
            {0, 6, 1, 5, 0, 0},
            {6, 0, 5, 0, 3, 0},
            {1, 5, 0, 5, 6, 4},
            {5, 0, 5, 0, 0, 2},
            {0, 3, 6, 0, 0, 6},
            {0, 0, 4, 2, 6, 0}};
    int** tempPtr;
    int numNodes = 6;
    printf("Preparing datarn");

    tempPtr = (int**)malloc(numNodes * sizeof(int*));
    for (i = 0; i < numNodes; i ++) {
        tempPtr[i] = (int*)malloc(numNodes * sizeof(int));
    }//Of for i

    for (i = 0; i < numNodes; i ++) {
        for (j = 0; j < numNodes; j ++) {
            if (myGraph[i][j] == 0) {
                tempPtr[i][j] = MAX_DISTANCE;
            } else {
                tempPtr[i][j] = myGraph[i][j];
            }//Of if
        }//Of for j
    }//Of for i

    printf("Data readyrn");

    NetPtr resultNetPtr = initNet(numNodes, tempPtr);
    return resultNetPtr;
}//Of constructSampleNet


void testPrim() {
    NetPtr tempNetPtr = constructSampleNet();
    printf("=====Dijkstra algorithm=====rn");
    dijkstraOrPrim(tempNetPtr, 0);
    printf("=====Prim algorithm=====rn");
    dijkstraOrPrim(tempNetPtr, 1);
}//Of testPrim


int main(){
    testPrim();
    return 1;
}//Of main

原本图

接下来着重对核心代码讲解

or (i = 0; i < numNodes - 1; i++) {
        // Step 2.1 Find out the best next node.
        minDistance = MAX_DISTANCE;
        for (j = 0; j < numNodes; j++) {
            // This node is visited.
            if (visitedArray[j]) {
                continue;
            } // Of if

            if (minDistance > distanceArray[j]) {
                minDistance = distanceArray[j];
                tempBestNode = j;
            } // Of if
        } // Of for j

        visitedArray[tempBestNode] = 1;

        // Step 2.2 Prepare for the next round.
        for (j = 0; j < numNodes ; j++) {
            // This node is visited.
            if (visitedArray[j]) {
                continue;
            } // Of if

            // This node cannot be reached.
            if (paraPtr->weights[tempBestNode][j] >= MAX_DISTANCE) {
                continue;
            } // Of if

 if (paraAlgorithm == 0) {
                if (distanceArray[j] > distanceArray[tempBestNode] + paraPtr->weights[tempBestNode][j]) {
                    // Change the distance.
                    distanceArray[j] = distanceArray[tempBestNode] + paraPtr->weights[tempBestNode][j];
                    // Change the parent.
                    parentArray[j] = tempBestNode;
                } // Of if
            } else {

  这是Dijkstra运行结果，追踪0距离

• the parent of each node: -1, 0, 0, 0, 2, 2,

• From node 0, path length to all nodes are: 0 (0), 1 (6), 2 (1), 3 (5), 4 (7), 5 (5),

• 当距离大于键入距离时，自动更换（注意，0距离视为无限距离）
• 比如在在对4检测时

发现从2到4最短，则自动更换，并将parent更换为2

而对于prim算法

else {
                if (distanceArray[j] > paraPtr->weights[tempBestNode][j]) {
                    // Change the distance.
                    distanceArray[j] = paraPtr->weights[tempBestNode][j];
                    // Change the parent.
                    parentArray[j] = tempBestNode;
                } // Of if
            }//Of if

箭头表示入度出度 ，简单来说，除0外（0开始visit)，被最优算法入度元素parent成为出度元素,且被入度标记为visit

下面详解，开始visit

for (i = 0; i < numNodes - 1; i++) {
        // Step 2.1 Find out the best next node.
        minDistance = MAX_DISTANCE;
        for (j = 0; j < numNodes; j++) {
            // This node is visited.
            if (visitedArray[j]) {
                continue;
            } // Of if

            if (minDistance > distanceArray[j]) {
                minDistance = distanceArray[j];
                tempBestNode = j;
            } // Of if
        } // Of for j

        visitedArray[tempBestNode] = 1;

        // Step 2.2 Prepare for the next round.
        for (j = 0; j < numNodes ; j++) {
            // This node is visited.
            if (visitedArray[j]) {
                continue;
            } // Of if

            // This node cannot be reached.
            if (paraPtr->weights[tempBestNode][j] >= MAX_DISTANCE) {
                continue;
            } // Of if

但注意每次该节点跳出固定其他节点距离

else {
        resultCost = 0;//
        for (i = 0; i < numNodes; i++) {
            resultCost += distanceArray[i];
            printf("cost of node %d is %d, total = %drn", i, distanceArray[i], resultCost);
        } // Of for i
        printf("Finally, the total cost is %d.rn ", resultCost);
    }//Of if

 在每次遍历中调整其距离

 Prim算法和Dijkstra算法是最小生成树和单源最短路径问题里面两个十分经典的算法，并且在我们计算机行业应用十分广泛，是基础算法。所以我们一定要掌握。代码里面有很详细的注释，如果不能很好的看懂理解的话，建议跟着图多跟踪几遍