当前位置：首页 > 编程日记 > 正文

【数据结构】所有顶点对的最短路径 Floyd算法

编程日记 2024-10-16 09:50:00

所有顶点对的最短路径问题是指：对于给定的有向图G=(V，E),求任意一对顶点之间的最短路径。

可以求解得到的 $A_{k+1}[i][j]$ 的递推公式：

$A_{-1}[i][j]=g.edges[i][j]$

$A_{k+1}[i][j]=min\begin{Bmatrix} A_{k}[i][j],A_{k}[i][k+1]+A_{k}[k+1][j] \end{Bmatrix}$

#include <stdio.h>
#include <stdlib.h>
const int FINITY = 5000;
const int M = 20;
typedef struct 
{char vex[M];int edges[M][M];int e,n;
}Mgraph;int dist[M][M];
int path[M][M];void creat (Mgraph *g,int c)
{int i,j,k,w;FILE *f;f=fopen("test.txt","r");if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++)fscanf(f,"%1s",&g->vex[i]);for(i=0;i<g->n;i++){for(j=0;j<g->n;j++){if(i==j)	g->edges[i][j]=0;else	g->edges[i][j]=FINITY;}}for(k=0;k<g->e;k++){fscanf(f,"%d%d%d",&i,&j,&w);g->edges[i][j]=w;if(c==0)	g->edges[j][i]=w;}fclose(f);}else{g->n=0;}
}void print(Mgraph g)
{int i,j;printf("%一共有%d个结点，%d条边\n",g.n,g.e);for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){printf("%-6d",g.edges[i][j]);}printf("\n");}
}void floyd(Mgraph g)
{int i,j,k;for(i=0;i<g.n;i++)//初始化{for(j=0;j<g.n;j++){dist[i][j]=g.edges[i][j];if(i!=j && dist[i][j]<FINITY){path[i][j]=i;}else{path[i][j]=-1;}}}for(k=0;k<g.n;k++){for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(dist[i][j]>(dist[i][k]+dist[k][j])){dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}}}}
}void find(Mgraph g)
{int a,b;int x;while(1){printf("\n请输入有向图中的任意两个顶点的序号：");scanf("%d%d",&a,&b);if(a<0 || a>=g.n || b<0 || b>=g.n){printf("顶点序号输入有误，请重新输入！！\n");continue;}printf("%c 和 %c 的最短路径长度是 %d\n",g.vex[a],g.vex[b],dist[a][b]);printf("是否继续？（1/0）\n请输入：");scanf("%d",&x);if(x!=1){exit(0);}}
}int main ()
{Mgraph g;creat(&g,1);print(g);floyd(g);find(g);printf("程序结束\n");return 0;
}

https://www.dkcj.cn/info/23276.html

backbone学习总结（二）

今天来看下backbone的路由控制的功能。其实个人感觉backbone，模块就那么几个，熟悉它的框架结构，以及组成，就差不多。废话不多说，我们来看看还剩下的功能。关于路由和历史管理通过 Backbone.Router.extend 来创建路由…

编程日记2024/10/16 09:40:00

人工智能--野人过河

课程简介人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好…

编程日记2024/10/16 09:30:00

java对cookie的操作

原文：http://www.cnblogs.com/muzongyan/archive/2010/08/30/1812552.html java对cookie的操作比较简单，主要介绍下建立cookie和读取cookie，以及如何设定cookie的生命周期和cookie的路径问题。建立一个无生命周期的cookie，即随着…

编程日记2024/10/16 09:20:00

【问题描述】 Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R u…

编程日记2024/10/16 09:10:00

sparkCore源码解析之思维脑图

2019独角兽企业重金招聘Python工程师标准>>> 在学习sparkCore时，有几个模块的概念理解不是很透彻，故对照源码进行学习，并将结果一脑图的形式呈现，方便后续的持续学习。详细内容见： sparkCore源码解析之blo…

编程日记2024/10/16 09:00:00

pangilin 安装编译

make pangolin 的时候报错 ootsun:/home/sun/AR/orb/Pangolin-0.5/build# make [ 1%] Building CXX object src/CMakeFiles/pangolin.dir/log/packetstream.cpp.o /home/sun/AR/orb/Pangolin-0.5/src/log/packetstream.cpp: 在函数‘void pangolin::WaitUntilPlaybackTim…

编程日记2024/10/16 08:50:00

PHP实现求阶乘

function factorial ($x){if ($x > 1) {$s $x * factorial ($x - 1);} else {$s $x;}return $s; }$x 100;echo $x."的阶乘的为".factorial($x);转载于:https://blog.51cto.com/chensenlin/1854679

编程日记2024/10/16 08:40:00

【ACM】杭电OJ 2064（汉诺塔III）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2064 思路： 1、将n-1个盘从A移到C f(n-1)次 2、将第n个从A移到B 1次 3、将n-1个盘从C移到A f(n-1)次 4、将第n个从B移到C 1次 5、将n-1个盘从A移到C f(n-1)次 #include<cstdio> #inclu…

编程日记2024/10/16 08:30:00

文件上传至阿里云

public static String uploadFile2OSS(InputStream instream, String fileName) throws IOException {String imageName null;OSSClient ossClient null;try {ClientConfiguration conf new ClientConfiguration();// 请求超时时间设置conf.setConnectionTimeout(5000);// 请…

编程日记2024/10/16 08:20:00

ORB-SLAM2安装

安装顺利与否可能会与Ubuntu版本有关。（ubuntu16.04 gcc4.8.5这个很重要偶，本班的直接决定Pangolin能不能安装成功，如果遇到哦问题的朋友可以参考一下链接 http://blog.csdn.net/Darlingqiang/article/details/78928873）亲测可用…

编程日记2024/10/16 08:10:00

iOS 系统分析（一）阅读内核准备知识

原文出自【听云技术博客】：http://blog.tingyun.com/web/a... 0x01 iOS体系架构1.1 iOS 系统的整体体系架构用户体验( The User Experience layer )：SpringBoard 同时支持 Spotlight。应用软件开发框架（The Application Frameworks layer&a…

编程日记2024/10/16 08:00:00

【数据结构】拓扑排序

如果一个有向图中没有包含简单的回路，这样的图为有向无环图。图中的顶点代表事件（活动），图中的有向边说明了事件之间的先后关系。这种用顶点表示活动，用弧表示活动时间的优先关系的有向图称为顶点表示活动的网&#…

编程日记2024/10/16 07:50:00

Java8自定义条件让集合分组

** 将一个指定类型对象的集合按照自定义的一个操作分组； 每组对应一个List、最终返回结果类型是:List<List<T>> param <T>*/static class GroupToList<T> implements Collector<T, List<List<T>>, List<List<T>&g…

编程日记2024/10/16 07:40:00

ROS_Kinetic ubuntu 16.04

ROS_Kinetic系列学习(一)，在ubuntu 16.04安装ROS Kinetic。 http://wiki.ros.org/kinetic/Installation/Ubuntu 通过网页快速了解Linux（Ubuntu）和ROS机器人操作系统，请参考实验楼在线系统如下： 纯净定制版镜像已经…

编程日记2024/10/16 07:30:00

android 获取手机GSM/CDMA信号信息,并获得基站信息

本文转自：http://software.intel.com/zh-cn/blogs/2011/12/16/android-gsmcdma/ 在Android中我们常用的轻松获取WIFI信号列表，那如何获取CDMA或者GSM的手机信号呢？系统提供了TelephonyManager类，此类非常丰富，基本你所…

编程日记2024/10/16 07:20:00

$e(i)$

【数据结构】关键路径

在有向图中，如果用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间，这样的活动称为边表示活动的网，简称AOE网（Activity On Edge）。通常可以用AOE网来估算工程的完成时间，他不…

编程日记2024/10/16 07:10:00

呼伦湖国家级自然保护区管理局投放草料保野生黄羊过冬

图为保护区工作人员正在观测黄羊的生活轨迹并记录数据。王艳清摄图为保护区工作人员正在观测黄羊的生活轨迹并记录数据。王艳清摄中新网呼伦贝尔1月16日电 (记者李爱平)中国北方正是最为寒冷的时节，呼伦湖国家级自然保护区管理局内的60只野生黄羊正在面临食草…

编程日记2024/10/16 07:00:00

buildroot httpd php

/********************************************************************* buildroot httpd php* 说明：* 在buildroot中选择了php，但是在测试的时候发现总是出现下面这行* 错误，库是存在的，但是却没有放对…

编程日记2024/10/16 06:50:00

VS快速注释多行以及取消

快速注释多行：Ctrl K 然后 Ctrl C 快速取消多行注释 ：Ctrl K 然后 Ctrl U

编程日记2024/10/16 06:40:00

前端的一些小的效果

1 . 移动端字体自适应大小（暂时没用过，不过据说很有用也很好用） body{font-family: "Microsoft YaHei";font-size: 0.14rem;color: #666;max-width: 640px;margin: auto;}media screen and (min-width: 360px) { html {font-s…

编程日记2024/10/16 06:30:00

Java虚拟机规范阅读(二)IEEE754简介以及Java虚拟机中的浮点算法

什么是浮点数在计算机系统的发展过程中，曾经提出过多种方法表达实数。典型的比如相对于浮点数的定点数（Fixed Point Number）。在这种表达方式中，小数点固定的位于实数所有数字中间的某个位置。货币的表达就可以使用这种方式&#…

编程日记2024/10/16 06:20:00

【ACM】杭电OJ 5055（Bob and math problem）

http://acm.hdu.edu.cn/showproblem.php?pid5055 注意几点： 1、全部都是偶数，输出-1 2、n-1个是0，第n个不论是奇数，还是偶数，输出-1 3、n1的情况 4、将所有数字从大到小排列，挑出最小的奇数放在最后…

编程日记2024/10/16 06:10:00

每天工作4小时的程序员【转】

每个人都熟悉这种作息规律：早上9点去上班，坐在电脑前面，编一天的程序，下午5点下班回家。如今，非常感谢蒂莫西费里斯 (Timothy Ferriss)的《每周工作4小时》，我开始重新思考应该如何工作，如何让自…

编程日记2024/10/16 06:00:00

ARKIT/ARCore对比分析(一)

ARKit简介 ARkit是什么？ 苹果为什么发布ARkit？（6月5日的苹果WWDC 2017全球开发者大会上，苹果发布了AR开发平台ARkit） 1.概述：ARkit应用平台是苹果的首个 AR 产品。iOS 11引入了ARKit应用平台，…

编程日记2024/10/16 05:50:00

每个程序员必看：如何在40岁后继续做软件开发？

导读: 这是一个 42 岁的开发者所写经验分享文章．并且列出一些他 18 年多身为软件开发者的经验谈．许多部分看完后都会希望自己当时就能够了解，所以很推荐不论是新手或是老手都要好好阅读这一篇文章。故事很长，一切从 1997 年开始讲…

编程日记2024/10/16 05:40:00

【ACM】杭电OJ 1009 （FatMouse' Trade）。

两个条件貌似缺一不可不明白为什么不能是sum（s[i].value*s[i].cat_food）； #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int maxn 1010;typedef …

编程日记2024/10/16 05:30:00

Java图形化：布局方式

布局方式 FlowLayout:流布局 BorderLayout:边框布局 GridLayout:网格布局FlowLayout（流布局） 像Word打字，组件从左向右排列，一列排满后自动换下一行。组件默认居中对齐，可以设置左/右对齐。流布局会维持组件的原始大小…

编程日记2024/10/16 05:20:00

ARKIT/ARCore对比分析(二)

ARKit(2) ARCore 和 ARKit平台特点比对曾与一家最大的 IMU OEM 交谈过，为了节省成本，他们的智能机IMU 在工厂中只是在单一温度下进行标定。这意味着 IMU 硬件在某一指定的温度下，误差被调节到最低。但当手机发热的时候，IMU 就不…

编程日记2024/10/16 05:10:00

【ACM】杭电OJ 1789（Doing Homework again）

http://acm.hdu.edu.cn/showproblem.php?pid1789 cmp函数： 先按扣分由多到少进行排序，然后如果遇到扣分一样的，则先做时间少的。 vis数组： 最要的事，放在它的截至日期那一天去做，然后，之后…

编程日记2024/10/16 05:00:00