最小生成树-迪杰斯特拉(Dijkstra)算法

奥普瓯江

原理：




备注：





算法：

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

#define MAX 65535
#define E 5

int dis[E][E] = {{0, 2, 4, 7, MAX},{2, 0, 1, MAX, 2},{4, 1, 0, 1, 6},{7, MAX, 1, 0, MAX},{MAX, 2, 6, MAX, 0}};
int main()
{

    int W[E] = {MAX, MAX, MAX, MAX, MAX};
    int D = 0, S = 0;

    for(int i = 0; i < E - 1; i++)
    {
        W[S] = 0;                               //当每一个以执行后的数组赋值为0

        for(int j = 0; j < E; j++)             //第一个循环，这个循环主要是用于比较和向W数组中赋值用的
        {
            if(W[j] != 0 && j != S)             //如果W[j]不等于0，同时j 不等于S及执行该判断
            {
                 if(W[j] == MAX || W[j] > D + dis[S][j])    //当W[j]数组中的数等于MAX最大值的时候就执行该判断或者W[j]数组大于传导节点的数值加上传导节点这一行中最小的数值及执行该判断
                {
                    W[j] = D + dis[S][j];                   //将传导节点中的数值D加上在dis数组中传导节点这一行中最小的值赋值给W[j]
                }
            }
        }

        D = MAX;                                //从新对D节点赋值因为上面的循环所用到的第一次循环D的赋值是O下面的循环其中的判断if（D > W[l]）的意思是在本次循环中找到W数组中最小的值并将他赋给D如果不赋值MAX那0就是最小的值该程序无法执行

        for(int l = 0; l < E; l++)             //再次进行循环赛选出W数组中最小的值并将数组中的数值以及下标分别传给D和S以备上一个循环使用
        {
            if(W[l] != 0 && W[l] != MAX)
            {
                if(D > W[l])
                {
                    D = W[l];                   //数组中的值赋给D

                    S = l;                      //下标赋给l
                }
            }
        }

        printf("%d ", W[S]);
    }

    return 0;
}

输出结果：

yinda_peng

离散数学的内容

yinda_peng

本质就是贪心，加了一个无回路的条件

奥普瓯江

yinda_peng 发表于 2023-4-28 20:42
本质就是贪心，加了一个无回路的条件

嗯嗯是的，最简单的方法得出了不一样的效果