首页 > 编程语言 >数据结构学习笔记-迪杰斯特拉算法

数据结构学习笔记-迪杰斯特拉算法

时间:2024-06-08 10:34:10浏览次数:27  
标签:dist int 路径 迪杰 SPTSet 算法 斯特拉 顶点 数据结构

最短路径问题的经典解法-dijsktra算法

问题描述:求从一个顶点到另一个顶点的最短路径

【算法设计思想】

Dijkstra算法的设计思想基于以下关键概念和步骤,旨在找出图中从一个给定的源顶点到其他所有顶点的最短路径。这个算法适用于有向和无向图,只要图的边权重为非负值。

1. 初始化

  • dist[]为一个数组,dist[i]表示从源顶点到顶点i的最短路径估计。初始时,对所有idist[i]设为无穷大,除了源顶点自身,其值设为0。
  • SPTSet[](最短路径树集合)为一个集合,用于记录已经被处理并且其最短路径已经被找到的顶点。最开始,这个集合为空。

2. 选择最小距离顶点

  • 在未处理的顶点集合中选择一个距离最小的顶点u,即dist[u]是最小的,并且u不在SPTSet中。最开始,这将会是源顶点。

3. 更新距离值

  • 对于顶点u的每个邻接顶点v,如果v不在SPTSet中,并且通过uv的路径长度小于当前记录的dist[v]的值,则更新dist[v]。更新规则是:dist[v] = dist[u] + weight(u, v),其中weight(u, v)是从uv的边的权重。

4. 标记为已处理

  • 将顶点u添加到SPTSet中,表示u的最短路径已经被找到。

5. 重复步骤

  • 重复步骤2至4,直到所有顶点都被处理,即SPTSet包含所有顶点。

【算法描述】

// 寻找最短路径树集合中距离最小的顶点
int minDistance(int dist[], int sptSet[]) {
    // 初始化最小值
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

// 使用Dijkstra算法找到图中源点到所有顶点的最短路径
void dijkstra(int graph[V][V], int src) {
    int dist[V]; // dist[i]会保存源点到i的最短路径距离
    int sptSet[V]; // sptSet[i]会为真如果顶点i在最短路径树中,或者最短距离从源点到i已经确认

    // 初始化所有距离为无穷大,sptSet[]为假
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

    // 源点到自己的距离总是0
    dist[src] = 0;

    // 寻找所有顶点的最短路径
    for (int count = 0; count < V - 1; count++) {
        // 从尚未处理的顶点集合中选取距离最小的顶点
        int u = minDistance(dist, sptSet);

        // 标记选取的顶点为已处理
        sptSet[u] = 1;

        // 更新选取顶点的邻接顶点的距离值
        for (int v = 0; v < V; v++)

            // 更新dist[v]只有在以下情况:未在sptSet中,存在从u到v的边,且源点到v的总距离小于当前dist[v]的值
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    // 打印构建的距离数组
    printSolution(dist);
}

【完整的测试程序】

#include <stdio.h>
#include <limits.h>

// 顶点数量
#define V 9

// 寻找最短路径树集合中距离最小的顶点
int minDistance(int dist[], int sptSet[]) {
    // 初始化最小值
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

// 打印构建的距离数组
void printSolution(int dist[]) {
    printf("顶点 \t 距离源点的距离\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}

// 使用Dijkstra算法找到图中源点到所有顶点的最短路径
void dijkstra(int graph[V][V], int src) {
    int dist[V]; // dist[i]会保存源点到i的最短路径距离
    int sptSet[V]; // sptSet[i]会为真如果顶点i在最短路径树中,或者最短距离从源点到i已经确认

    // 初始化所有距离为无穷大,sptSet[]为假
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

    // 源点到自己的距离总是0
    dist[src] = 0;

    // 寻找所有顶点的最短路径
    for (int count = 0; count < V - 1; count++) {
        // 从尚未处理的顶点集合中选取距离最小的顶点
        int u = minDistance(dist, sptSet);

        // 标记选取的顶点为已处理
        sptSet[u] = 1;

        // 更新选取顶点的邻接顶点的距离值
        for (int v = 0; v < V; v++)

            // 更新dist[v]只有在以下情况:未在sptSet中,存在从u到v的边,且源点到v的总距离小于当前dist[v]的值
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    // 打印构建的距离数组
    printSolution(dist);
}

int main() {
    // 例子中图的邻接矩阵表示法
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};

    dijkstra(graph, 0);

    return 0;
}

标签:dist,int,路径,迪杰,SPTSet,算法,斯特拉,顶点,数据结构
From: https://www.cnblogs.com/zeta186012/p/18238371

相关文章

  • 二叉树-数据结构
    父节点地址值左子节点地址右子节点地址每一个节点往下面,都是会分成左右两个树的结点度,就是子节点的数量二叉树就是生活中的树的概念树的高度是以最大的数量去数小的往左边放,大的往右边放以根节点为坐标,小于根节点的储存在左边,大的根节点放在右边和根节点相等的数,我们......
  • 红黑树-数据结构
    平衡二叉B树每个节点可以是红或者是黑红黑树不是高度平衡的,他的平衡是“通过自己的红黑规则实现的”红黑规则每个节点是红或者为黑根节点必须是黑色如果一个节点没有子节点或者是父节点,这个节点的相应的指针属性为nil,这些nil视为叶节点,每个叶节点nil是黑色的如果某个节......
  • 【数据结构】图论入门
    引入数据的逻辑结构:集合:数据元素间除“同属于一个集合”外,无其他关系线性结构:一个对多个,例如:线性表、栈、队列树形结构:一个对多个,例如:树图形结构:多个对多个,例如:图图的基本概念及术语图:G=(V,E)V:顶点(数据元素)的有穷非空集合E:边的有穷集合图的类型定义无向图:每......
  • 数据结构学习笔记-佛洛依德算法
    最短路径问题的经典解法-佛洛依德算法问题描述:设计算法求解图的最短路径【算法设计思想】初始化距离矩阵:首先,将解决方案矩阵dist[][]初始化为输入图矩阵graph[][],这个矩阵存储了顶点之间的直接距离或者权值。中间顶点迭代:然后,对每一个顶点作为中间顶点进行迭代。算法通过......
  • C++数据结构之:哈希表Hash
    摘要:  it人员无论是使用哪种高级语言开发东东,想要更高效有层次的开发程序的话都躲不开三件套:数据结构,算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储......
  • C++数据结构之:图Graph
    摘要:  it人员无论是使用哪种高级语言开发东东,想要更高效有层次的开发程序的话都躲不开三件套:数据结构,算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结......
  • ClickHouse内幕(2)基础数据结构
    ClickHouse以性能好被大家所熟知,而一个数据库的性能优化是一个庞大的系统性工程。本文着眼于ClickHouse内部的基础数据结构,以揭露ClickHouse性能优化的冰山一角。在软件工程中并不是所有的执行路径都需要优化,只有关键执行路径才需要花费大力气进行优化。对于数据库领域来说关键执......
  • 【数据结构】栈和队列-->理解和实现(赋源码)
    Toc欢迎光临我的Blog,喜欢就点歌关注吧♥前面介绍了顺序表、单链表、双向循环链表,基本上已经结束了链表的讲解,今天谈一下栈、队列。可以简单的说是前面学习的一特殊化实现,但是总体是相似的。前言栈是一种特殊的线性表,它只允许在一端进行插入和删除操作。这一端被称为......
  • 数据结构与算法-17_排序算法
    文章目录1.概述比较排序算法非比较排序算法稳定vs不稳定Java中排序2.冒泡排序3.选择排序4.堆排序5.插入排序6.希尔排序7.归并排序递归实现时间复杂度非递归实现8.归并+插入9.快速排序随机基准点处理重复值10.计数排序11.桶排序12.基数排序习题E01.根据另一个数组......
  • 数据结构学习笔记-归并排序
    归并排序算法的设计与分析问题描述:设计并分析归并排序算法【算法设计思想】分割(Divide):从中间分割数组,使每个子数组包含一半的元素。这通过计算中点m来完成,通常是(l+r)/2,但为了防止大数溢出,使用l+(r-l)/2。解决(Conquer):递归地对两个子数组应用归并排序,直到......