算法的思想:
分析题目要求，我们可以得知：算法要实现找到一条花费在1500元以下的最短的路径。其中这里面涉及两个变量，一个是路径的长度，要求最短。一个是花费，要求不大于1500元。基于这两个变量的不同的要求，本算法实现了两种分支限定的方法。对于”距离”变量，由于要求其最短，故使用优先级队列的分支限界法，可保证算法沿优先级最高(在这里也就是当前节点到起点距离最短的节点)向前进行搜索，这样就可以保证第一次搜索到达终点的路径，就是最短路径。对于”花费”变量，算法首先计算图中的每一个点到达终点的最少花费(使用的是改进的Floyd算法)。记录在minCost[51]数组中，对于当前正在搜索的节点，如果当前点到达起点的费用+当前点到达终点的费用之和大于1500元，则进行剪枝。除上述两个重要的思想外，本算法还使用动态规划的思想：也就是在搜寻过程中，若我们发现有两条路径可到达同一点，我们便可放弃到达那一点成本较高的路径而对这条路径停止搜寻。
算法中的使用的数据结构:
CArcItem：代表访问的城市，也就是状态空间树中的状态节点
class CArcItem
{
int
m_CityID;                      //当前访问的城市序号[1-50]
int
m_dDisToStart;                    //起始城市到当前访问城市的路径长度
int
m_dCostToStart;                  //起始城市到当前访问城市所需费用
CArcItem
* m_pParentArcItem;       //生成的最短路径树中的父节点
}
CPriorityQueu：优先级队列，采用二叉堆实现，对城市状态空间树中的状态节点(也就是城市)按照当前访问城市到起始城市的距离进行升序排序，使当前访问城市到起始城市的距离最小的节点始终在二叉堆的堆顶，也就是优先级最高。
minCost[51]数组：记录图中所有节点到达终点的最小花费。初始化在Floyd()方法中实现。
哈希表：DomSet：记录当前城市ID和当前城市到达起点城市”最小距离”,这里之所以加引号，是因为这个最小距离是随着搜索的进行而不断的减小的，也就是在搜寻过程中，若我们发现有两条路径可到达同一城市，我们便可放弃到达那一点成本较高的路径而对这条路径停止搜寻。
openTable保存所有已生成而未考察的节点，
closeTable记录已访问过的节点。
算法流程图：
程序主要代码

动态规划：多段图最短路径
cost[8]=C89+cost[9]=3 path[8]=9
cost[7]=C79+cost[9]=7 path[8]=9
cost[6]=min{C68+cost[8]}=8 path[6]=8
cost[5]=min{C57+cost[7],C58+cost[8]}=9 path[5]=8
8+7 , 6+3
cost[4]=min{C47+cost[7],C48+cost[8]}=9 path[4]=8
5+7 ,6+3
cost[3]=min{C35+cost[5],C36+cost[6]}=13 path[3]=5
cost[2]=min{C23+cost[3],C24+cost[4],C26+cost[6]}=14 path[2]=3
cost[1]=min{C14+cost[4],C15+cost[5]}=17 path[1]=5
cost[0]=min{C01+cost[1],C02+cost[2]}=15 path[0]=2
path[0]=2
path[2]=3
path[3]=5
path[5]=8
path[8]=9
最短路径为：0-2-3-5-8-9
---以下代码使用的是Java语言(Java写的顺手了o(∩_∩)o...)
//多段图求最短路径
class Cost{
int C=0;
int costId=0;
public Cost(){}
public Cost(int C,int costC,int id){
this.C=C+costC;
this.costId=id;
}
}
public class Graphic {
static int node[][]={
//0,1,2,3,4,5,6,7,8,9
{0,4,1,0,0,0,0,0,0,0},
{0,0,0,0,9,8,0,0,0,0},
{0,0,0,1,0,7,8,0,0,0},
{0,0,0,0,0,4,7,0,0,0},
{0,0,0,0,0,0,0,5,6,0},
{0,0,0,0,0,0,0,8,6,0},
{0,0,0,0,0,0,0,0,5,0},
{0,0,0,0,0,0,0,0,0,7},
{0,0,0,0,0,0,0,0,0,3},
{0,0,0,0,0,0,0,0,0,0}
};
static Cost [] cost=new Cost[10];
static Cost [] dis=new Cost[10];
static int [] path=new int[10];
public static int C(int a,int b){
return node[a][b];
}//
public static void show(){
for(int i=0;i
for(int j=0;j
System.out.print(node[i][j]+" ");
}
System.out.println();
}
}//
public static void initCost(){
for(int i=0;i
cost[i]=new Cost();
}
}//
public static void initDis(){
for(int i=0;i
dis[i]=new Cost();
}
}//
public static int plength(Cost dis[]){
int num=0;
for(int i=0;i
if(dis[i].C==0){
num=i;
break;
}
}
return num;
}
public static int plength(int dis[]){
int num=0;
for(int i=0;i
if(dis[i]==0){
num=i;
break;
}
}
return num;
}
public static Cost min(Cost dis[],int length){//取最小值
Cost m=new Cost();
m.C=9999;
for(int i=0;i
if(dis[i].C
m.C=dis[i].C;
m.costId=dis[i].costId;
}
}
return m;
}//
public static int[] goPoints(int start){//返回可到达哪些点
int [] p={0,0,0,0,0,0,0,0,0,0};
int counter=0;
for(int y=0;y
if(node[start][y]!=0){
p[counter]=y;
counter++;
}
}
return p;
}//
public static void process(){//核心算法
initCost();
for(int i=8;i>=0;i--){
initDis();
for(int j=0;j
int [] p=goPoints(i);
dis[j]=new Cost(C(i,p[j]),cost[p[j]].C,p[j]);
}
//
cost[i]=min(dis,plength(dis));
path[i]=cost[i].costId;
}
}//
public static void output(){//输出 距离 及 路径
System.out.println("0-9最短距离为："+cost[0].C);
System.out.println("路径如下：");
int t=path[0];
System.out.print("0"+"-");
do{
System.out.print(t+"-");
t=path[t];
}while(t<9);
System.out.print("9");
}
public static void main(String[] args){
show();
process();
for(int i=0;i
System.out.println("cost"+i+":"+cost[i].C+"   "+"path"+i+":"+path[i]);
}
output();
}
}

求最短路径众所周知有Dijistra算法、Bellman-ford等，除了这些算法，用动态规划也可以求出最短路径，时间复杂度为O(n^2)，
跟没有优化的Dijistra算法一样(优化后的Dijistra算法时间复杂度为O((m+n)lgn))。
左侧1-15表示前一个节点，最上面一行1-15表示后一个节点，记这个图的矩阵为P，那么P[0][1]==5表示节点0与节点1相连
，路径长度为5。那么我们如何利用动态规划来求解最短路径？
首先我们需要把整个问题转换成小的子问题，利用小的子问题的最优解求出整个问题的最优解。
我们的目的是求0-15之间的最短路径，由图可知与节点15相连的是结点14和节点13，假设我们已经求出0-13的最短路径的值D13和0-14的最短路径的值D14，
那么我们只需要比较D13+d(13-15)和D14+d(14-15)的大小就可以知道从哪个节点出发到节点15的路径最短。
按照这个思想一直往前推，推到节点0时结束，自然就求出了节点0-节点15的最短路径，这个思路是递归的，
如果用递归的方法，时间复杂度很高，当然你也可以用备忘录，记录已经计算过的值，我这里将递归转换成迭代。
我们先定义一个类class Node,里面存储节点的序号、从0到这个节点的最短路径的值、前一个节点的序号。
class node{
public int number;
//value是指从0到这个节点总共要走多远，执行算法前将value的值初始化为无穷大
public int value;
public int parent;
}
最后将n[15].value打印出来就是最短路径的值，
再根据parent的值往前找就得到最短路径的解，当然这个例子有不同的路径的解，虽然值一样，我这里只给了一种。
class node {
int value = Integer.MAX_VALUE;
int parent;
}
public class Check {
public static void main(String[] args) {
node[] n = new node[16];
for (int i = 0; i < 16; i++) {
n[i] = new node();
}
int[][] array = {
{ 0, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 3, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 8, 7, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 6, 8, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 3, 5, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 8, 4, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 2, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};
for (int i = 0; i < 16; i++) {
for (int j = i + 1; j < 16; j++) {
if (array[i][j] != 0) {
int temp = n[i].value + array[i][j];
if (temp< n[j].value) {
// System.out.println(i+" "+j+" "+d+" "+n[j].value);
n[j].value =temp;
n[j].parent = i;
}
}
}
}
int i = 15;
System.out.print(15 + " ");
while (i > 0) {
System.out.print(n[i].parent + " ");
// i--;
i = n[i].parent;
}
}
}

Floyd算法
Floyd是一种经典的多源最短路径算法，它通过动态规划的思想来寻找给定加权图中的多源点之间的最短路径，算法时间复杂度是O(n3)。之所以叫Floyd是因为该算法发明人之一是Robert Floyd，他是1978年图灵奖获得者，同时也是斯坦福大学计算机科学系教授。
核心思想
对于n个点的加权图，从加权图的权值矩阵开始，递归地更新n次最终求得每两点之间的最短路径矩阵。即加权图的邻接矩阵为 $D = (d_{ij}){_{nn}}$ 按一定公式对该矩阵进行递归更新，初始时矩阵为D(0)，第一次，根据公式用D(0)构建出矩阵D(1)；第二次，根据公式用D(1)构建出矩阵D(2)；以此类推，根据公式用D(n-1)构造出矩阵D(n)，D(n)即为图的距离矩阵，i行j列表示顶点i到顶点j的最短距离。
动态规划
如何理解这种动态规划算法呢？可以理解为逐一选择中转点，然后针对该中转点，所有以此为中转点的其它点都要根据规定进行更新，这个规定就是原来两点之间的距离如果通过该中转点变小了则更新距离矩阵。比如选择“1”作为中转点，原来“02”之间的距离为5，通过中转点1后(即路径变为“012”)距离为4，变小了，那么就更新距离矩阵对应的元素，由5更新为4。当图中所有顶点都被作为中转点处理以后，那么得到的最后距离矩阵就是多源最短距离矩阵了。
设 $c(i,j,k)$ 为i到j的中间节点编号不超过k的最短距离，当k=0时，$c(i,j,0)=d_{ij} $，对于n个顶点的图，我们要求的i到j的最短距离即是$c(i,j,n−1)$。
现在我们建立 $c(i,j,k)c(i,j,k) c(i,j,k)$ 之间的递归关系，对于任意k，$c(i,j,k)=min(c(i,j,k−1),c(i,k,k−1)+c(k,j,k−1))$，于是可以根据该递归关系得到最终的最短路径，即中间节点编号不超过n-1的最短距离。
算法过程
从任意一条单边路径开始，所有两点之间的距离是边的权重，如果两点之间没有边相连，则权重为无穷大。即用数组  $D = (d_{ij}){_{nn}}$ 来记录i,j之间的最短距离，初始时，若i=j则dis[i][j]=0。若i、j两点之间相连则dis[i][j]的值为该边的权值。若i、j两点没有相连则dis[i][j]的值为无穷。
对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短，如果存在则更新。即对所有的k值(1
神奇的五行代码
Floyd算法核心就是下列五行代码，可以体会一下，三个for循环嵌套，最外层的k即是循环取不同中转点时的情况，分别让图中每个顶点作为中转点去更新距离，完成所有循环后就是最终的最短距离矩阵。
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(d[i][k]+d[k][j]
d[i][j]=d[i][k]+d[k][j];
优缺点
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。对于稠密图效果最佳，边权可正可负。
缺点：时间复杂度比较高，不适合计算大量数据。
执行过程
对于一个拥有7个顶点的无向加权图，分别用0-6来表示图的每个顶点，每条边上的数字为对应的权重。
首先根据每条边的权重来初始化距离矩阵，这是一个[7x7]的矩阵，行列分别对应两个顶点，比如第0行第1列表示顶点0到顶点1，对应的值为3，即权值为3。以此类推，其它元素分别代表对应边的权重。
当以顶点0为中转点时
逐一查找看是否有以0为中转点使得距离更短，实际上并不用比较所有矩阵的元素，只需比较满足if (i != j && j != k && i != k)条件的元素，即都为0的对角线和中转点对应的行列不用比较，因为对角线上的元素表示顶点自己到自己的距离，所以无需比较，而中转点对应的行列表示顶点到中转点的距离，也无需比较。
比较d[1][2]与d[1][0]+d[0][2]，因为1<3+5，所以不更新d[1][2]。
往下，比较d[1][3]与d[1][0]+d[0][3]，因为4<3+INF，所以不更新d[1][3]。
往下，比较d[1][4]与d[1][0]+d[0][4]，因为INF<3+INF，所以不更新d[1][4]。接着往下d[1][5]、d[1][6]两个元素情况类似。
比较d[2][1]与d[2][0]+d[0][1]，因为1<3+5，所以不更新d[2][1]。
往下，比较d[2][3]与d[2][0]+d[0][3]，因为4<5+INF，所以不更新d[2][3]。
往下，比较d[2][4]与d[2][0]+d[0][4]，因为8<5+INF，所以不更新d[2][4]。
往下，比较d[2][5]与d[2][0]+d[0][5]，因为2<5+INF，所以不更新d[2][5]。
往下，比较d[2][6]与d[2][0]+d[0][6]，因为INF<5+INF，所以不更新d[2][6]。
比较d[3][1]与d[3][0]+d[0][1]，因为4
类似地，剩下的元素全部都不更新，最后比较完d[6][5]与d[6][0]+d[0][5]后即完成了以0作为中转点的全部比较工作。
当以顶点1为中转点时
逐一查找看是否有以1为中转点使得距离更短，比较d[0][2]与d[0][1]+d[1][2]，
因为5>3+1，所以将d[0][2]的值更新为4。
比较d[0][3]与d[0][1]+d[1][3]，
因为INF>3+4，所以将d[0][3]的值更新为7。
第0行接着的三个元素都不更新，到第2行后，比较d[2][0]与d[2][1]+d[1][0]，
因为5>1+3，所以将d[2][0]的值更新为4。第二行剩余的元素都无需更新。
开始第3行，比较d[3][0]与d[3][1]+d[1][0]，
因为INF>4+3，所以将d[3][0]的值更新为7。
接着以顶点1作为中转点时剩余的全部元素都无需更新。
当以顶点2为中转点时
逐一查找看是否有以2为中转点使得距离更短，比较d[0][1]与d[0][2]+d[2][1]，因为3<4+1，所以d[0][1]不更新。
比较d[0][3]与d[0][2]+d[2][3]，因为7<4+4，所以d[0][3]不更新。
比较d[0][4]与d[0][2]+d[2][4]，
因为INF>4+8，所以将d[0][4]的值更新为12。
类似地，对以顶点2作为中转点的全部剩余元素进行比较更新。
当以顶点3为中转点时
逐一查找看是否有以3为中转点使得距离更短，比较d[0][1]与d[0][3]+d[3][1]，因为3<7+4，所以d[0][1]不更新。
比较d[0][2]与d[0][3]+d[3][2]，因为4<7+4，所以d[0][2]不更新。
类似地，对以顶点3作为中转点的全部剩余元素进行比较更新。
当以顶点4为中转点时
逐一查找看是否有以4为中转点使得距离更短，比较d[0][1]与d[0][4]+d[4][1]，因为3<12+9，所以d[0][1]不更新。
比较d[0][2]与d[0][4]+d[4][2]，因为4<12+8，所以d[0][2]不更新。
类似地，对以顶点4作为中转点的全部剩余元素进行比较更新。
当以顶点5为中转点时
逐一查找看是否有以5为中转点使得距离更短，比较d[0][1]与d[0][5]+d[5][1]，因为3<6+3，所以d[0][1]不更新。
比较d[0][2]与d[0][5]+d[5][2]，因为4<6+2，所以d[0][2]不更新。
类似地，对以顶点5作为中转点的全部剩余元素进行比较更新。
当以顶点6为中转点时
逐一查找看是否有以6为中转点使得距离更短，比较d[0][1]与d[0][6]+d[6][1]，因为3<9+6，所以d[0][1]不更新。
比较d[0][2]与d[0][6]+d[56][2]，因为4<9+5，所以d[0][2]不更新。
类似地，对以顶点6作为中转点的全部剩余元素进行比较更新。
最终矩阵
将所有顶点作为中转点处理后，最终得到了一个矩阵，这个矩阵就是图的每个顶点两两最短距离矩阵。比如a[0][4]=12就是顶点0到顶点4的最短距离为12。同时可以看到距离矩阵是以对角线为轴对称的。