Dandelion's uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards.  The workers will compare their rewards ,and some one may have demands of…

2018年1月26日 0条评论 4点热度 阅读全文

拓扑排序 有向无环图      如果一个有向图的任意顶点都无法通过一些有向边回到自身,那么称这个有向图为有向无环图。 拓扑排序      拓扑排序是将有向无环图G的所有顶点排成一个线性序列,使得对图G中的任意两个顶点u、v,如果存在边u->v,那么在序列中u一定在v前面,这个序列又被称为拓扑序列。 如下图:结点0和1没有前驱节点,可以任意访问,但是结点2必须在结点0和1访问完之后才能访问,同理结点3和4必须在结点2访问完以后才能访问,但是结点3和4 …

2017年8月18日 0条评论 0点热度 阅读全文

求最短路径问题之Dijkstra算法(二) (4)、Dijkstra算法求解实际问题 之前讲的是最基本的Dijkstra算法,那么平时考试笔试等遇到的题目肯定不会这么“裸”,更多时候会出现这样一种情况,即从起点到终点的最短距离最小的路径不止一条。 那么碰到这种两条以上可以达到最短距离的路径,题目就会给出一个第二标尺(第一标尺是距离),要求在所有最短路径中选择第二标尺最优的一条路径,而第二标尺常见的是以下三种出题方法或者其组合: 给每条边在增加一个边权(比如说花费),然后要求在最短路径有多条时要求路径上的花费之和最小…

2017年7月2日 0条评论 1点热度 阅读全文

求最短路径之Dijkstra算法 Dijkstra算法是用来求单源最短路径问题,即给定图G和起点s,通过算法得到s到达其他每个顶点的最短距离。 基本思想:对图G(V,E)设置集合S,存放已被访问的顶点,然后每次从集合V-S中选择与起点s的最短距离最小的一个顶点(记为u),访问并加入集合S。之后,令u为中介点,优化起点s与所有从u能够到达的顶点v之间的最短距离。这样的操作执行n次(n为顶点个数),直到集合S已经包含所有顶点。 Dijkstra算法伪代码:   //G为图;数组d为源点到达各点的最短路径长度,…

2017年7月2日 0条评论 9点热度 阅读全文

Dijkstra算法用来寻找图的结点间最短路径,通常是指定一个起始结点后,寻找从该结点出发,到达各个结点的最短路径。该算法是有关最短路径问题的一个算法。由Dijkstra于1959年提出。 百度百科:Dijkstra算法。 维基百科:Dijkstra's Algorithm。 参考链接:Dijkstra算法的C语言程序。 程序说明:图存储在二维数组中,即邻接矩阵中。使用s集合和vs集合辅助Dijkstra算法的过程,开始时将指定的开始结点放入s集合中,其他剩余的结点放入vs集合中,从s集合到vs集合的边中找出一个代…

2017年3月2日 0条评论 5点热度 阅读全文

Dijikstra算法是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。该算法是由荷兰计算机科学家迪杰斯特拉于1959年提出的。 程序来源:Dijkstra's Algorithm。 百度百科:Dijkstra算法。 维基百科:Dijkstra's Algorithm。 C语言程序(去除了原文中非标准的C语言代码): #include<stdio.h> #define INFINITY 9999 #define MAX 10 void dijikstra(int G[MAX][MAX…

2017年2月4日 0条评论 3点热度 阅读全文

本文给出了C++程序和Python程序。 tarjan算法是由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。 程序来源:Tarjan’s Algorithm to find Strongly Connected Components。 百度百科: tarjan算法。 维基百科:Tarjan's strongly connected components algorithm。  参考文章:Tarjan算法。 C++程序: // A C++ program to find strongly co…

2017年2月4日 0条评论 7点热度 阅读全文

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <string> #include <iostream> #include <sstream> #include <ostream> #include <algorithm> #include <ctype.h> #include <cmath> #include…

2016年7月15日 0条评论 0点热度 阅读全文

这里讨论下RIP和OSPF的基本算法,在CISCO课程中讨论RIP和OSPF的区别有不少,但是回溯源头,它们理论算法里面的原理差不多,比较大的区别主要有三点 1.Bellman-ford的链路距离是估算的,Dijkstra是传输链路距离给邻居的。PS:这就说明了为什么RIP要采用跳数,而OSPF用的是cost,也就是带宽作为主要参数,因为估计在具体实现中是不大可行的,故采用不同的具体度量值。 2.Bellman-ford的持续进行链路距离的计算,而Dijkstra只进行一次计算就可以了,这点可能表达的不是太准确,大…

2015年3月10日 0条评论 0点热度 阅读全文

这里讨论下RIP和OSPF的基本算法,在CISCO课程中讨论RIP和OSPF的区别有不少,但是回溯源头,它们理论算法里面的原理差不多,比较大的区别主要有三点 1.Bellman-ford的链路距离是估算的,Dijkstra是传输链路距离给邻居的。PS:这就说明了为什么RIP要采用跳数,而OSPF用的是cost,也就是带宽作为主要参数,因为估计在具体实现中是不大可行的,故采用不同的具体度量值。 2.Bellman-ford的持续进行链路距离的计算,而Dijkstra只进行一次计算就可以了,这点可能表达的不是太准确,大…

2015年3月10日 0条评论 0点热度 阅读全文