单源最短路径问题实验参考报告

好东西

实验题目：单源最短路径问题 2010年11月18日

告诉您寝的人 下周二（13周）做实验 记得写~~~~

实验目的：

1．明确单源最短路径问题的概念；

2．利用贪心算法解决单源最短路径问题；

3．通过本例熟悉贪心算法在程序设计中的应用方法。

实验内容

给定一个带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各点的最短路长度。 实验原理

在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策。

Dijkstra算法是解决单源最短路径问题的贪心算法。设置顶点集合S并不断作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径已知。初始时S中只含源。设u为G中一顶点，从源点到u且中间只经过S中的顶点的路称为从源到u特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。 每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解 。

算法实现

#include <iostream>

using namespace std;

#define MAX 999

void getdata(int **c,int n)

{

int i,j;

int begin,end,weight;

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

{

if(i==j)

c[i][j]=0;

else

好东西

c[i][j]=MAX;

}

}

do {

cout<<"请输入 起点 终点 权值(-1退出)：";

cin>>begin;

if(begin==-1) break;

cin>>end>>weight;

c[begin][end]=weight;

} while(begin!=-1);

}

void Dijkstra(int n,int v ,int *dist,int *prev,int **c)

{

bool s[MAX];

int i,j;

for (i=1;i<=n;i++)

{

dist[i]=c[v][i]; //从源点到各点的值

s[i]=false;

if(dist[i]==MAX) prev[i]=0; //最大值没有路径

else prev[i]=v; //前驱为源点

}

dist[v]=0;s[v]=true;

for (i=1;i<=n;i++)

{

int temp=MAX;

int u=v;

for(j=1;j<=n;j++)

if((!s[j])&&(dist[j]<temp)) {u=j;temp=dist[j];}//不在集合里，值《temp，选最小值

s[u]=true;

for (j=1;j<=n;j++)

{

if((!s[j])&&(c[u][j]<MAX))

{

int newdist=dist[u]+c[u][j];

if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}//前驱u记录下来

}

}

}

好东西

void PrintPath(int *prev,int n,int begin,int end)

{

int *path=new int [n+1];

int i,m=n;

bool k=true;

path[end]=end;

for(i=end-1;i>1;i--)

{

path[i]=prev[path[i+1]]; //构造路径

m--;

}

for (i=m;i<=end;i++) {

cout<<path[i]<<"->"; //输出路径

}

cout<<"\b\b"<<" "<<endl;

}

void main()

{

int n,i;

int v=1;

cout<<"请输入顶点个数：";

cin>>n;

int *dist=new int [n+1];

int *prev=new int [n+1];

int **c;

c=new int *[n+1];

for (i=0;i<=n;i++)

{

c[i]=new int [n+1];

}

getdata(c,n); //获取数据

int begin=1,end;

cout<<"请输入所求单源路径的 起点 终点：";

cin>>begin>>end;

好东西

} Dijkstra(n,v,dist,prev,c); //计算路径 PrintPath(prev,n,begin,end); //输出路径

实验思考题：

1.简述贪心算法的基本思想及算法实现过程？

基本思路:

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。 算法实现过程：

1.从问题的某一初始解出发；

2.当能朝给定总目标前进一步，求出可行解的一个解元素；

3.由所有解元素组合成问题的一个可行解。