问题描述

无向连通图计算最短路径C++实现

设G(V,E)是一个无向连通图，s,t是它的两个不同的结点。 G(V,E)的每个结点或者着红色，或者着兰色。试设计一个求从s到t经过兰色结点数最少的路经的算法。

解决方案

http://www.cnblogs.com/aiyelinglong/archive/2012/03/26/2418707.html

解决方案二：

无法通过步进的方式找到这个问题的最优解，贪心不能用，但是可以用动态规划求解全局最优解而不需要列出所有解

解决方案三：

一种比较笨的方法，把兰色和红色节点分开存放，假如分别为A，B，先在B中判断s，t是否连通，若不连通，从A里依次加入一个，两个，三个...兰色节点，直到s，t连通为止