【算法设计与分析】— —单源最短路径的贪心算法

简介: 【算法设计与分析】— —单源最短路径的贪心算法

🎯目的:


1)了解贪心算法思想及基本原理;


2)掌握使用贪心算法求解问题的一般特征;


3)能够针对实际问题,能够正确选择贪心策略;


4)能够针对选择的贪心策略,证明算法的正确性;


5)能够根据贪心策略,正确编写代码;


6)能够正确分析算法的时间复杂度和空间复杂度。

🎯内容:

单源最短路径的贪心算法。

测试数据可选用下图,1为源点:

🎯代码(Java):

package one;
 
public class Three {
 
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int x1[][] = { { 0, 2, 0, 1, 0, 3, 0, 0 }, { 0, 0, 6, 0, 5, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 6 },
        { 0, 10, 0, 0, 0, 0, 2, 0 }, { 0, 0, 9, 0, 0, 0, 0, 4 }, { 0, 0, 0, 5, 0, 0, 4, 0 },
        { 0, 7, 0, 0, 3, 0, 0, 8 }, { 0, 0, 0, 0, 0, 0, 0, 0 } };
    int s = 1;// 表示原点
    int[] dist = new int[x1.length];// 表示原点到各点的最短距离
    boolean[] visited = new boolean[x1.length];
    int [] pre=new int[x1.length];//记录最短路径的前驱结点
    for (int i = 0; i < x1.length; i++) {// 初始化
      dist[i] = Integer.MAX_VALUE;// 初始化为无穷大
      visited[i] = false;// 初始化为没有被访问过
      pre[i]=-1;//前去初始化为-1
    }
    dist[s - 1] = 0;// 自身到自身为0
 
    // 找原点到各个顶点的距离
    for (int i = 0; i < x1.length; i++) {
      int mindist = Integer.MAX_VALUE;// 最短路径
      int mindistindex = -1;// 最短路径的索引
      // 寻找路径中最短的
      for (int j = 0; j < x1.length; j++) {
        if (!(visited[j]) && dist[j] < mindist) {
          // 更新数据
          mindist = dist[j];
          mindistindex = j;
        }
      }
      visited[mindistindex] = true;// 将顶点添加到已访问数组中
      // 更新最短距离
      for (int j = 0; j < x1.length; j++) {
        if (!visited[j] && x1[mindistindex][j] != 0 && dist[mindistindex] != Integer.MAX_VALUE
            && dist[mindistindex] + x1[mindistindex][j] < dist[j]) {
          dist[j] = dist[mindistindex] + x1[mindistindex][j];// 更新最短距离
          pre[j]=mindistindex+1;//记录前驱结点
        }
      }
    }
    System.out.printf("顶点:  ");
    for (int i = 0; i < x1.length; i++) {
      System.out.printf((i+1)+"   ");
    }
    System.out.println();
    System.out.printf("距离:       ");
    for (int i = 1; i < x1.length; i++) {
      System.out.printf(dist[i]+"   ");
    }
    System.out.println();
    System.out.printf("前驱:       ");
    for (int i = 1; i < x1.length; i++) {
      System.out.printf(pre[i]+"   ");
    }
  }

🎯运行结果:

🎯 算法分析:


时间复杂度:


  • 初始化阶段:需要遍历所有的顶点,时间复杂度为O(n)。
  • 最短路径查找阶段:需进行n次迭代,每次迭代需要遍历所有顶点,时间复杂度为O(n^2),因此,总体时间复杂度为O(n^2)。


空间复杂度:


  • 使用了四个数组,其中x1占用了O(n^2)的空间,dist,visited,pre占用各自O(n)的空间。因此,空间复杂度为O(n^2)。

       需要注意的是,时间复杂度和空间复杂度的分析是基于给定图的规模为n的情况下。在实际应用中,如果图的规模非常大,可以考虑采用优化算法或数据结构来减小时间和空间的开销。


🎯其他程序语言的实现:

以下代码均有ai生成,读者如发现bug可以发在评论区,咱们一起解决❤️!

🎐C语言程序:

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
 
#define SIZE 8 // 矩阵大小
 
void dijkstra(int graph[SIZE][SIZE], int source) {
    int dist[SIZE];     // 原点到各点的最短距离
    bool visited[SIZE]; // 记录节点是否被访问
    int pre[SIZE];      // 记录最短路径的前驱结点
 
    for (int i = 0; i < SIZE; i++) {
        dist[i] = INT_MAX;      // 初始化为无穷大
        visited[i] = false;     // 初始化为没有被访问过
        pre[i] = -1;            // 前驱初始化为-1
    }
 
    dist[source - 1] = 0; // 自身到自身为0
 
    // 找原点到各个顶点的距离
    for (int i = 0; i < SIZE; i++) {
        int minDist = INT_MAX; // 最短路径
        int minDistIndex = -1; // 最短路径的索引
 
        // 寻找路径中最短的
        for (int j = 0; j < SIZE; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minDistIndex = j;
            }
        }
 
        visited[minDistIndex] = true; // 将顶点添加到已访问数组中
 
        // 更新最短距离
        for (int j = 0; j < SIZE; j++) {
            if (!visited[j] && graph[minDistIndex][j] != 0 && dist[minDistIndex] != INT_MAX &&
                dist[minDistIndex] + graph[minDistIndex][j] < dist[j]) {
                dist[j] = dist[minDistIndex] + graph[minDistIndex][j]; // 更新最短距离
                pre[j] = minDistIndex + 1; // 记录前驱结点
            }
        }
    }
 
    printf("顶点:  ");
    for (int i = 0; i < SIZE; i++) {
        printf("%d   ", i + 1);
    }
    printf("\n");
 
    printf("距离:       ");
    for (int i = 1; i < SIZE; i++) {
        printf("%d   ", dist[i]);
    }
    printf("\n");
 
    printf("前驱:       ");
    for (int i = 1; i < SIZE; i++) {
        printf("%d   ", pre[i]);
    }
}
 
int main() {
    int graph[SIZE][SIZE] = {
        {0, 2, 0, 1, 0, 3, 0, 0},
        {0, 0, 6, 0, 5, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 6},
        {0, 10, 0, 0, 0, 0, 2, 0},
        {0, 0, 9, 0, 0, 0, 0, 4},
        {0, 0, 0, 5, 0, 0, 4, 0},
        {0, 7, 0, 0, 3, 0, 0, 8},
        {0, 0, 0, 0, 0, 0, 0, 0}
    };
 
    int source = 1; // 表示原点
    dijkstra(graph, source);
 
    return 0;
}


🎐python程序:

import sys
 
def dijkstra(x1, s):
    dist = [sys.maxsize] * len(x1) # 表示原点到各点的最短距离
    visited = [False] * len(x1)
    pre = [-1] * len(x1) # 记录最短路径的前驱结点
    dist[s - 1] = 0 # 自身到自身为0
 
    for _ in range(len(x1)):
        mindist = sys.maxsize # 最短路径
        mindistindex = -1 # 最短路径的索引
        # 寻找路径中最短的
        for j in range(len(x1)):
            if not visited[j] and dist[j] < mindist:
                # 更新数据
                mindist = dist[j]
                mindistindex = j
        visited[mindistindex] = True # 将顶点添加到已访问数组中
        # 更新最短距离
        for j in range(len(x1)):
            if not visited[j] and x1[mindistindex][j] != 0 and dist[mindistindex] != sys.maxsize and dist[mindistindex] + x1[mindistindex][j] < dist[j]:
                dist[j] = dist[mindistindex] + x1[mindistindex][j] # 更新最短距离
                pre[j] = mindistindex + 1 # 记录前驱结点
 
    print("顶点:", end=" ")
    for i in range(len(x1)):
        print(i + 1, end=" ")
    print()
    
    print("距离:", end="    ")
    for i in range(1, len(x1)):
        print(dist[i], end=" ")
    print()
    
    print("前驱:", end="    ")
    for i in range(1, len(x1)):
        print(pre[i], end=" ")
    print()
 
if __name__ == "__main__":
    x1 = [[0, 2, 0, 1, 0, 3, 0, 0],
          [0, 0, 6, 0, 5, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 0, 6],
          [0, 10, 0, 0, 0, 0, 2, 0],
          [0, 0, 9, 0, 0, 0, 0, 4],
          [0, 0, 0, 5, 0, 0, 4, 0],
          [0, 7, 0, 0, 3, 0, 0, 8],
          [0, 0, 0, 0, 0, 0, 0, 0]]
    s = 1 # 表示原点
    dijkstra(x1, s)


       请注意,Python中没有类似Java中的整型溢出问题,因此使用了sys.maxsize作为无穷大。另外,Python的索引是从0开始的,所以在输出时顶点和索引都需要加1。希望对你有所帮助!如有其他问题,请随时问我。


🎐C++程序:

#include<iostream>
using namespace std;
int main(){
    int x1[8][8]={{0,2,0,1,0,3,0,0},
                   {0,0,6,0,5,0,0,0},
                   {0,0,0,0,0,0,0,6},
                   {0,10,0,0,0,0,2,0},
                   {0,0,9,0,0,0,0,4},
                   {0,0,0,5,0,0,4,0},
                   {0,7,0,0,3,0,0,8},
                   {0,0,0,0,0,0,0,0}};
    int s=1;
    const int n=8;
    int dist[n],pre[n];
    bool visited[n];
    for(int i=0;i<n;i++){
        dist[i]=INT_MAX;
        visited[i]=false;
        pre[i]=-1;
    }
    dist[s-1]=0;
    for(int i=0;i<n;i++){
        int mindist=INT_MAX,mindistindex=-1;
        for(int j=0;j<n;j++){
            if(!visited[j]&&dist[j]<mindist){
                mindist=dist[j];
                mindistindex=j;
            }
        }
        visited[mindistindex]=true;
        for(int j=0;j<n;j++){
            if(!visited[j]&&x1[mindistindex][j]!=0&&dist[mindistindex]!=INT_MAX&&dist[mindistindex]+x1[mindistindex][j]<dist[j]){
                dist[j]=dist[mindistindex]+x1[mindistindex][j];
                pre[j]=mindistindex+1;
            }
        }
    }
    cout<<"顶点:  ";
    for(int i=0;i<n;i++){
        cout<<i+1<<"   ";
    }
    cout<<endl;
    cout<<"距离:       ";
    for(int i=1;i<n;i++){
        cout<<dist[i]<<"   ";
    }
    cout<<endl;
    cout<<"前驱:       ";
    for(int i=1;i<n;i++){
        cout<<pre[i]<<"   ";
    }
    cout<<endl;
    return 0;
}
相关文章
|
23天前
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
1天前
|
供应链 算法 搜索推荐
从公布的前十一批其他算法备案通过名单分析
2025年3月12日,国家网信办发布算法备案信息,深度合成算法通过395款,其他算法45款。前10次备案中,深度合成算法累计3234款,其他类别647款。个性化推送类占比49%,涵盖电商、资讯、视频推荐;检索过滤类占31.53%,用于搜索优化和内容安全;调度决策类占9.12%,集中在物流配送等;排序精选类占8.81%,生成合成类占1.55%。应用领域包括电商、社交媒体、物流、金融、医疗等,互联网科技企业主导,技术向垂直行业渗透,内容安全和多模态技术成新增长点。未来大模型检索和多模态生成或成重点。
从公布的前十一批其他算法备案通过名单分析
|
2天前
|
人工智能 自然语言处理 供应链
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。
|
20天前
|
算法 Java 调度
算法系列之贪心算法
在算法中,贪心算法(Greedy Algorithm)是一种常见的解决优化问题的算法。贪心算法的核心思想是:在每一步选择中都采取当前状态下最优的选择,即贪心的做出局部最优的决策,从而希望最终能够得到全局最优解。尽管贪心算法并不总是能够得到全局最优解,但在许多实际问题中,它能够提供足够好的解决方案,并且具有较高的计算效率。
45 7
算法系列之贪心算法
|
16天前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
29 3
|
3天前
|
人工智能 自然语言处理 算法
从第九批深度合成备案通过公示名单分析算法备案属地、行业及应用领域占比
2024年12月20日,中央网信办公布第九批深度合成算法名单。分析显示,教育、智能对话、医疗健康和图像生成为核心应用领域。文本生成占比最高(57.56%),涵盖智能客服、法律咨询等;图像/视频生成次之(27.32%),应用于广告设计、影视制作等。北京、广东、浙江等地技术集中度高,多模态融合成未来重点。垂直行业如医疗、教育、金融加速引入AI,提升效率与用户体验。
|
23天前
|
存储 算法 测试技术
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
|
2月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
3月前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
69 6
|
4月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
107 1

热门文章

最新文章