实验目的:通过分枝限界法求得单源最短路径的最优解,来熟悉分枝限界法的
搜索策略和设计策略。
实验源代码:
#include <iostream>
#include<conio.h>
using namespace std;
#define MAX 9999
/* Graph 类,用以存放有关图的所有信息 */
class Graph
{
public:
void ShorestPaths(int);
Graph();
private:
int n; //图的节点个数
int *prev; //存放顶点的前驱节点
int **c; //存放图的邻接矩阵
int *dist; //存放源点到各个顶点的距离
};
/*节点*/
class MinHeapNode
{
friend Graph;
public:
int getI() {return i;}
void setI(int ii)
{
i = ii;
}
int getLength(){return length;}
void setLength(int len)
{
length = len;
}
private:
int i; //顶点编号
int length; //当前路长
};
/* 最小堆 */
class MinHeap
{
评论5
最新资源