单源最短路径（贪心法）实验报告

算法分析与设计实验报告

第 5 次实验

姓名 时间 实验名称 12.12下午 贪心法求最短路径 学号 地点 四合院 班级 实验目的 通过上机实验，掌握贪心算法的思想，利用 Dijkstra 算法求解最短路 径并实现。 使用贪心法求出给定图各点的最短路径，并计算算法的执行时间，分析 算法的有效性。 实验原理 已知一个有向网络 G=(V,E)和源点 V1，如上所示，求出从 源点出发到图中其余顶点的最短路径。 1 用邻接矩阵表示有向图，并进行初始化，同时选择源点； 2 选取候选集中距离最短的顶点，把其加入终点集合中； 3 以该顶点为新考虑的中间顶点，修改候选集中各顶点距离，若经过该点 后，各点到达源点距离比原来距离短，则修改距离； 4 重复以上 2、3 步，直到所有候选集点都被加入到终点集中。 void Dijkstra(int n,int v,int dist[],int prev[]){ bool s[maxint]; for(int i=1;i<=n;i++){ dist[i]=c[v][i]; s[i]=false; if(dist[i]==maxint) prev[i]=0; else prev[i]=v; } //找到第一个可行源点 s[]标志，记录prev[]前一个点 dist[v]=0; s[v]=true; for(int i=1;i

附录：完整代码

#include #include #include

#define maxint 1000 int c[200][200]={0};

void Dijkstra(int n,int v,int dist[],int prev[]){ bool s[maxint];

for(int i=1;i<=n;i++){ dist[i]=c[v][i]; s[i]=false;

if(dist[i]==maxint) prev[i]=0; else prev[i]=v;

} //找到第一个可行源点 s[]标志，记录prev[]前一个点 dist[v]=0; s[v]=true;

for(int i=1;i

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

if((!s[j])&&(dist[j]

temp=dist[j]; } }

s[u]=true;

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

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

}

int main(){ int n,v;

printf(\请输入顶点数： \ scanf(\

//printf(\路径： \ srand(time(0));

for(int i=1;i

/* scanf(\///手动输入 if(i!=j){

if((c[j][i]==0)||(c[j][i]==1000)) c[i][j]=rand()0+1; else c[i][j]=1000;

if(c[i][j]>50) c[i][j]=1000; } } }

printf(\请输入源点： \ scanf(\

int dist[n+1],prev[n+1];

printf(\路径：\\n\ for(int i=1;i

printf(\ printf(\ }

Dijkstra(n,v,dist,prev); for(int i=1;i

printf(\到%d的最短路径为：%d\ } }