最短路径的算法及其应用:
算法有很多,包括上面没有讲到的和讲到的:
SSSP(单源最短路径):1.标号法 2.Dijkstra(可以用heap优化) 3.Bellman_ford(可以检测负环) 4.SPFA(可以检测负环,还可以继续优化,不过还没学)
所有点对的最短路径:1.可以求N次SSSP 2.Floyd算法
该章提到的应用问题:
1. 求图的中心点:
中心点定义:找出一个顶点,使得其到所有其他的顶点的最短路径的最大值最小。
求法:求出所有顶点对的最短路径,求出每个顶点到其他所有顶点的最短路径的最大值,从中选出最小的那个,用Floyd算法求解,时间复杂度为O(N^3).
代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int inf = 0xffffff;
const int MAXN = 110;
#define MIN(a,b) (a)>(b)?(b):(a)
int g[MAXN][MAXN],d[MAXN][MAXN];
void init()
{
memset(g,0,sizeof(g));
}
void Floyd(int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(g[i][j])d[i][j]=g[i][j];
else d[i][j]=inf;
if(i==j)d[i][j]=0;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
d[i][k] = MIN(d[i][k],d[i][j]+d[j][k]);
}
}
}
}
int CenterPoint(int n)
{
int best=inf+1,best_i;
for(int i=0;i<n;i++)
{
int max = -1;
for(int j=0;j<n;j++)
{
if(d[i][j]>max)
{
max = d[i][j];
}
}
if(max<best)
{
best = max;
best_i = i;
}
}
return best_i;
}
int main()
{
int n;
init();
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>g[i][j];
}
}
Floyd(n);
int point = CenterPoint(n);
cout<<point<<endl;
system("pause");
return 0;
}
2.求图的P中心点:
P中心点的定义:记图的顶点集V的一个含有P个元素的子集为S,使得集合V-S中的顶点到S中顶点的最短路径的最大值最小的集合S,就是图的P中心点。
求法:求出所有顶点对的最短路径,枚举S的每一种情况,记录下集合V-S中的顶点到S中顶点的最短路径的最大值,然后从所有的情况中选出最小的种顶点的组
合方式,就是图的P中心点。
注意:需要枚举排列,复杂度很高,目前还没有有效算法。
代码略。
3.求图的中央点:
中央点的定义:记顶点V到其他各顶点的最短距离为d(x),每前进单位距离需要的代价为k,使得 所有的 k*d(x)的和最小的顶点就是图的中央点。
求法:求出所有顶点对的最短路径,求出每个顶点到其他所有顶点的(最短路径*代价)的和,选出使得该和最小的顶点,就是图的中央点。用Floyd算法,时
间复杂度为O(N^3).
代码(把前面代码的CenterPoint换成该函数即可,这里K取1)
int ZhongYangPoint(int n)
{
int best = inf,best_i;
for(int i=0;i<n;i++)
{
int sum = 0;
for(int j=0;j<n;j++)
{
sum+=d[i][j];
}
if(sum<best)
{
best = sum;
best_i = i;
}
}
return best_i;
}
分享到:
相关推荐
《图论的算法与程序设计》(作者)吴文虎 清华大学 1997年3月第1版
《程序设计基础第二版》由吴文虎撰写,是一本以C/C++语言为背景,讲解编程思维和方法的教科书。书中涵盖了计算机语言、数据结构和常见算法等多个核心主题,旨在帮助读者掌握编程的基本技能,培养逻辑思维和实践能力...
学习acm必备 吴文虎 王建德的图论必备书籍
本书是和吴文虎编著的枟程序设计基础(第 2 版)枠(清华大学出版社 2004 年出版)配合使用的参考 书 。 内容包括 2部分 :第 1部分包括了枟程序设计基础(第 2 版)枠书中全部习题和参考解答 ;第 2 部分 ...
吴文虎教授以其深入浅出的教学风格,使得这套课件不仅在清华大学内部广受欢迎,也对全国乃至全球的C++学习者提供了宝贵的教育资源。 C++是现代计算机科学中不可或缺的一部分,是一种静态类型的、编译式的、通用的、...
【程序设计基础】是计算机科学领域中的核心课程之一,它为初学者提供了构建软件和解决实际问题的基础。吴文虎教授的C++课件正是针对这个...通过吴文虎教授的课件,初学者可以期待一个既有趣又富有挑战性的学习过程。
### 清华大学导师吴文虎简介及相关研究知识点 #### 一、导师简介 吴文虎教授是清华大学计算机科学与技术系智能技术与系统国家重点实验室语音技术中心的成员。他在语音信号处理领域有着深入的研究,并发表了多篇...
1. **算法设计**:算法是解决问题的步骤或规程,本书涵盖了各种经典算法,如排序(冒泡排序、插入排序、快速排序、归并排序等)、搜索(二分查找、广度优先搜索、深度优先搜索等)以及图论算法(最短路径算法...
这个是吴文虎的C语言课件PPT,现在只上传了一章。
《计算机网络》第五版吴文虎编著的课后习题答案涵盖了计算机网络的基础知识,对学习者提供了宝贵的参考资料。本章主要讨论了计算机网络的基本概念、交换技术以及因特网的发展历程和标准制定。 首先,计算机网络的...
【吴文虎教授的教学理念】 吴文虎教授是清华大学的一位教育专家,他的教学观念深受多元智能理论的影响。他强调课堂教学是实施素质教育的核心途径,教师应当珍惜每一分课堂时间,高效地完成教学任务。他认为,教师的...
C++程序设计是一门深入计算机科学基础的重要课程,由清华大学教授吴文虎主讲的这门课件,为学习者提供了宝贵的教育资源。吴文虎教授在C++领域有着丰富的教学和实践经验,他的讲解深入浅出,深受学生喜爱。这份课件...
《程序设计基础》 吴文虎 清华大学出版社 此版本是讲义ppt
吴文虎《程序设计基础第2版》PPT编程准备C++源代码一般都由若干函数和类组成。为了便于管理,一般把不同功能的函数和类放在不同的文件中,对于类的声明和实现也分别放在对应的.h(或.hpp)和.cpp文件中。
《吴文虎程序设计基础 课件》是针对C++编程语言的一套全面且优秀的教学资源,由知名教育专家吴文虎教授倾力打造。这套课件深入浅出地介绍了程序设计的基础概念,旨在帮助初学者掌握C++的核心知识,为后续的软件开发...
1. **基础算法**:包括排序(如冒泡排序、快速排序、归并排序)、搜索(如线性搜索、二分搜索)以及图论和树型结构算法等。 2. **数据结构**:如数组、链表、栈、队列、哈希表、树(二叉树、平衡树如AVL和红黑树)...
《程序设计基础》是计算机科学领域的一门入门课程,由著名计算机教育专家吴文虎教授编写,清华大学出版社出版。这门课程旨在引导初学者进入编程世界,通过学习基础的编程概念、语法和逻辑,培养解决问题的能力。...
《计算机语言与程序设计基础》...通过吴文虎讲师的《计算机语言与程序设计基础》课程,学生不仅可以掌握编程语言的基本语法,还能培养逻辑思维能力,学习如何有效地解决问题,并为后续的计算机科学学习打下坚实的基础。