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

    🎃欢迎大家前去观看我的算法设计与分析专栏： 算法设计与分析_IT闫的博客-CSDN博客 希望对大家有所帮助！

    🎃个人专栏：

    🐬 算法设计与分析：算法设计与分析_IT闫的博客-CSDN博客

    🐳Java基础：Java基础_IT闫的博客-CSDN博客

    🐋c语言：c语言_IT闫的博客-CSDN博客

    🐟MySQL：数据结构_IT闫的博客-CSDN博客

    🐠数据结构：​​​​​​数据结构_IT闫的博客-CSDN博客

    💎C++：C++_IT闫的博客-CSDN博客

    🥽C51单片机：C51单片机（STC89C516）_IT闫的博客-CSDN博客

    💻基于HTML5的网页设计及应用：基于HTML5的网页设计及应用_IT闫的博客-CSDN博客​​​​​​

    🥏python：python_IT闫的博客-CSDN博客

    欢迎收看，希望对大家有用！

    目录

    🎯目的：

    🎯内容：

     🎯代码（Java）：

    🎯运行结果：

    🎯 算法分析：

    🎯其他程序语言的实现：

    🎐C语言程序：

    🎐python程序：

    🎐C++程序：

    🎯目的：

    1）了解贪心算法思想及基本原理；

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

    3）能够针对实际问题，能够正确选择贪心策略；

    4）能够针对选择的贪心策略，证明算法的正确性；

    5）能够根据贪心策略，正确编写代码；

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

    🎯内容：

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

    测试数据可选用下图，1为源点：

     🎯代码（Java）：

    1. package one;
    2.  
    3. public class Three {
    4.  
    5. 	public static void main(String[] args) {
    6. 		// TODO Auto-generated method stub
    7. 		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 },
    8. 				{ 0, 10, 0, 0, 0, 0, 2, 0 }, { 0, 0, 9, 0, 0, 0, 0, 4 }, { 0, 0, 0, 5, 0, 0, 4, 0 },
    9. 				{ 0, 7, 0, 0, 3, 0, 0, 8 }, { 0, 0, 0, 0, 0, 0, 0, 0 } };
    10. 		int s = 1;// 表示原点
    11. 		int[] dist = new int[x1.length];// 表示原点到各点的最短距离
    12. 		boolean[] visited = new boolean[x1.length];
    13. 		int [] pre=new int[x1.length];//记录最短路径的前驱结点
    14. 		for (int i = 0; i < x1.length; i++) {// 初始化
    15. 			dist[i] = Integer.MAX_VALUE;// 初始化为无穷大
    16. 			visited[i] = false;// 初始化为没有被访问过
    17. 			pre[i]=-1;//前去初始化为-1
    18. 		}
    19. 		dist[s - 1] = 0;// 自身到自身为0
    20.  
    21. 		// 找原点到各个顶点的距离
    22. 		for (int i = 0; i < x1.length; i++) {
    23. 			int mindist = Integer.MAX_VALUE;// 最短路径
    24. 			int mindistindex = -1;// 最短路径的索引
    25. 			// 寻找路径中最短的
    26. 			for (int j = 0; j < x1.length; j++) {
    27. 				if (!(visited[j]) && dist[j] < mindist) {
    28. 					// 更新数据
    29. 					mindist = dist[j];
    30. 					mindistindex = j;
    31. 				}
    32. 			}
    33. 			visited[mindistindex] = true;// 将顶点添加到已访问数组中
    34. 			// 更新最短距离
    35. 			for (int j = 0; j < x1.length; j++) {
    36. 				if (!visited[j] && x1[mindistindex][j] != 0 && dist[mindistindex] != Integer.MAX_VALUE
    37. 						&& dist[mindistindex] + x1[mindistindex][j] < dist[j]) {
    38. 					dist[j] = dist[mindistindex] + x1[mindistindex][j];// 更新最短距离
    39. 					pre[j]=mindistindex+1;//记录前驱结点
    40. 				}
    41. 			}
    42. 		}
    43. 		System.out.printf("顶点：  ");
    44. 		for (int i = 0; i < x1.length; i++) {
    45. 			System.out.printf((i+1)+"   ");
    46. 		}
    47. 		System.out.println();
    48. 		System.out.printf("距离：       ");
    49. 		for (int i = 1; i < x1.length; i++) {
    50. 			System.out.printf(dist[i]+"   ");
    51. 		}
    52. 		System.out.println();
    53. 		System.out.printf("前驱：       ");
    54. 		for (int i = 1; i < x1.length; i++) {
    55. 			System.out.printf(pre[i]+"   ");
    56. 		}
    57. 	}

    🎯运行结果：

    🎯 算法分析：

    时间复杂度：

    • 初始化阶段：需要遍历所有的顶点，时间复杂度为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语言程序：

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. #define SIZE 8 // 矩阵大小
    6.  
    7. void dijkstra(int graph[SIZE][SIZE], int source) {
    8.     int dist[SIZE];     // 原点到各点的最短距离
    9.     bool visited[SIZE]; // 记录节点是否被访问
    10.     int pre[SIZE];      // 记录最短路径的前驱结点
    11.  
    12.     for (int i = 0; i < SIZE; i++) {
    13.         dist[i] = INT_MAX;      // 初始化为无穷大
    14.         visited[i] = false;     // 初始化为没有被访问过
    15.         pre[i] = -1;            // 前驱初始化为-1
    16.     }
    17.  
    18.     dist[source - 1] = 0; // 自身到自身为0
    19.  
    20.     // 找原点到各个顶点的距离
    21.     for (int i = 0; i < SIZE; i++) {
    22.         int minDist = INT_MAX; // 最短路径
    23.         int minDistIndex = -1; // 最短路径的索引
    24.  
    25.         // 寻找路径中最短的
    26.         for (int j = 0; j < SIZE; j++) {
    27.             if (!visited[j] && dist[j] < minDist) {
    28.                 minDist = dist[j];
    29.                 minDistIndex = j;
    30.             }
    31.         }
    32.  
    33.         visited[minDistIndex] = true; // 将顶点添加到已访问数组中
    34.  
    35.         // 更新最短距离
    36.         for (int j = 0; j < SIZE; j++) {
    37.             if (!visited[j] && graph[minDistIndex][j] != 0 && dist[minDistIndex] != INT_MAX &&
    38.                 dist[minDistIndex] + graph[minDistIndex][j] < dist[j]) {
    39.                 dist[j] = dist[minDistIndex] + graph[minDistIndex][j]; // 更新最短距离
    40.                 pre[j] = minDistIndex + 1; // 记录前驱结点
    41.             }
    42.         }
    43.     }
    44.  
    45.     printf("顶点：  ");
    46.     for (int i = 0; i < SIZE; i++) {
    47.         printf("%d   ", i + 1);
    48.     }
    49.     printf("\n");
    50.  
    51.     printf("距离：       ");
    52.     for (int i = 1; i < SIZE; i++) {
    53.         printf("%d   ", dist[i]);
    54.     }
    55.     printf("\n");
    56.  
    57.     printf("前驱：       ");
    58.     for (int i = 1; i < SIZE; i++) {
    59.         printf("%d   ", pre[i]);
    60.     }
    61. }
    62.  
    63. int main() {
    64.     int graph[SIZE][SIZE] = {
    65.         {0, 2, 0, 1, 0, 3, 0, 0},
    66.         {0, 0, 6, 0, 5, 0, 0, 0},
    67.         {0, 0, 0, 0, 0, 0, 0, 6},
    68.         {0, 10, 0, 0, 0, 0, 2, 0},
    69.         {0, 0, 9, 0, 0, 0, 0, 4},
    70.         {0, 0, 0, 5, 0, 0, 4, 0},
    71.         {0, 7, 0, 0, 3, 0, 0, 8},
    72.         {0, 0, 0, 0, 0, 0, 0, 0}
    73.     };
    74.  
    75.     int source = 1; // 表示原点
    76.     dijkstra(graph, source);
    77.  
    78.     return 0;
    79. }

    🎐python程序：

    1. import sys
    2.  
    3. def dijkstra(x1, s):
    4.     dist = [sys.maxsize] * len(x1) # 表示原点到各点的最短距离
    5.     visited = [False] * len(x1)
    6.     pre = [-1] * len(x1) # 记录最短路径的前驱结点
    7.     dist[s - 1] = 0 # 自身到自身为0
    8.  
    9.     for _ in range(len(x1)):
    10.         mindist = sys.maxsize # 最短路径
    11.         mindistindex = -1 # 最短路径的索引
    12.         # 寻找路径中最短的
    13.         for j in range(len(x1)):
    14.             if not visited[j] and dist[j] < mindist:
    15.                 # 更新数据
    16.                 mindist = dist[j]
    17.                 mindistindex = j
    18.         visited[mindistindex] = True # 将顶点添加到已访问数组中
    19.         # 更新最短距离
    20.         for j in range(len(x1)):
    21.             if not visited[j] and x1[mindistindex][j] != 0 and dist[mindistindex] != sys.maxsize and dist[mindistindex] + x1[mindistindex][j] < dist[j]:
    22.                 dist[j] = dist[mindistindex] + x1[mindistindex][j] # 更新最短距离
    23.                 pre[j] = mindistindex + 1 # 记录前驱结点
    24.  
    25.     print("顶点：", end=" ")
    26.     for i in range(len(x1)):
    27.         print(i + 1, end=" ")
    28.     print()
    29.     
    30.     print("距离：", end="    ")
    31.     for i in range(1, len(x1)):
    32.         print(dist[i], end=" ")
    33.     print()
    34.     
    35.     print("前驱：", end="    ")
    36.     for i in range(1, len(x1)):
    37.         print(pre[i], end=" ")
    38.     print()
    39.  
    40. if __name__ == "__main__":
    41.     x1 = [[0, 2, 0, 1, 0, 3, 0, 0],
    42.           [0, 0, 6, 0, 5, 0, 0, 0],
    43.           [0, 0, 0, 0, 0, 0, 0, 6],
    44.           [0, 10, 0, 0, 0, 0, 2, 0],
    45.           [0, 0, 9, 0, 0, 0, 0, 4],
    46.           [0, 0, 0, 5, 0, 0, 4, 0],
    47.           [0, 7, 0, 0, 3, 0, 0, 8],
    48.           [0, 0, 0, 0, 0, 0, 0, 0]]
    49.     s = 1 # 表示原点
    50.     dijkstra(x1, s)

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

    🎐C++程序：

    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5.     int x1[8][8]={{0,2,0,1,0,3,0,0},
    6.                    {0,0,6,0,5,0,0,0},
    7.                    {0,0,0,0,0,0,0,6},
    8.                    {0,10,0,0,0,0,2,0},
    9.                    {0,0,9,0,0,0,0,4},
    10.                    {0,0,0,5,0,0,4,0},
    11.                    {0,7,0,0,3,0,0,8},
    12.                    {0,0,0,0,0,0,0,0}};
    13.     int s=1;
    14.     const int n=8;
    15.     int dist[n],pre[n];
    16.     bool visited[n];
    17.     for(int i=0;i
    18.         dist[i]=INT_MAX;
    19.         visited[i]=false;
    20.         pre[i]=-1;
    21.     }
    22.     dist[s-1]=0;
    23.     for(int i=0;i
    24.         int mindist=INT_MAX,mindistindex=-1;
    25.         for(int j=0;j
    26.             if(!visited[j]&&dist[j]
    27.                 mindist=dist[j];
    28.                 mindistindex=j;
    29.             }
    30.         }
    31.         visited[mindistindex]=true;
    32.         for(int j=0;j
    33.             if(!visited[j]&&x1[mindistindex][j]!=0&&dist[mindistindex]!=INT_MAX&&dist[mindistindex]+x1[mindistindex][j]
    34.                 dist[j]=dist[mindistindex]+x1[mindistindex][j];
    35.                 pre[j]=mindistindex+1;
    36.             }
    37.         }
    38.     }
    39.     cout<<"顶点：  ";
    40.     for(int i=0;i
    41.         cout<1<<"   ";
    42.     }
    43.     cout<
    44.     cout<<"距离：       ";
    45.     for(int i=1;i
    46.         cout<"   ";
    47.     }
    48.     cout<
    49.     cout<<"前驱：       ";
    50.     for(int i=1;i
    51.         cout<"   ";
    52.     }
    53.     cout<
    54.     return 0;
    55. }
  • 相关阅读:
    一起Talk Android吧（第三百七十五回：如何使用ViewPager2）
    MQ高级-服务异步通信
    ProTable高级表格获取表单数据
    （免费领源码）hadoop#Mysql离线与实时的离线与实时的电影推荐系统10338-计算机毕业设计项目选题推荐
    设计模式浅析(六) ·命令模式
    用了10年开源工具，换了Smartbi后，3分钟搞定一份报表
    【2024】深度学习配置环境常见报错，持续更新中....
    【小程序】导航栏和内容页面联动效果实现
    分析java.lang.IncompatibleClassChangeError
    SSM框架（SpringBoot快速构建）
  • 原文地址：https://blog.csdn.net/shsjssnn/article/details/133687973