实验四贪心算法求解最短路径问题实验目的：1）以解决最短路径问题为例，掌握贪心算法的基本设计策略；2）掌握Dijkstra贪心法求解单源点最短路径问题并实现；3）分析实验结果。

实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.准备实验数据假设算法要处理下图，需要把图数据组织存放到相应的数据结构中，如：权值矩阵float graph[maxsize][maxsize]。

2.实现Dijkstra算法代码:#include <iostream>#include <fstream>#include <string>using namespace std;const int N = 6;const int M = 1000;ifstream fin("e://4d5.txt");ofstream fout("e://dijkstra-output1.txt");template<class Type>void Dijkstra(int n,int v,Type dist[],int prev[],Type c[][N+1]);void Traceback(int v,int i,int prev[]);//输出最短路径v源点，i终点int main(){int v = 1;//源点为1int dist[N+1],prev[N+1],c[N+1][N+1];cout<<"有向图权的矩阵为："<<endl;for(int i=1; i<=N; i++){for(int j=1; j<=N; j++){fin>>c[i][j];cout<<c[i][j]<<" ";}cout<<endl;}Dijkstra(N,v,dist,prev,c);for(int i1=2; i1<=N; i1++){fout<<"源点1到点"<<i1<<"的最短路径长度为:"<<dist[i1]<<"，其路径为";cout<<"源点1到点"<<i1<<"的最短路径长度为:"<<dist[i1]<<"，其路径为";Traceback(1,i1,prev);cout<<endl;fout<<endl;}return 0;}template<class Type>void Dijkstra(int n,int v,Type dist[],int prev[],Type c[][N+1]){bool s[N+1];for(int i=1; i<=n; i++){dist[i] = c[v][i];//dist[i]表示当前从源到顶点i的最短特殊路径长度s[i] = false;if(dist[i] == M){prev[i] = 0;//记录从源到顶点i的最短路径i的前一个顶点}else{prev[i] = v;}}dist[v] = 0;s[v] = true;for(int i1=1; i1<n; i1++){int temp = M;int u = v;//上一顶点//取出V-S中具有最短特殊路径长度的顶点ufor(int j=1; j<=n; j++){if((!s[j]) && (dist[j]<temp)){u = j ;temp = dist[j];}}s[u] = true;//根据作出的贪心选择更新Dist值for(int j1=1; j1<=n; j1++){if((!s[j1]) && (c[u][j1]<M)){Type newdist = dist[u] + c[u][j1];if(newdist < dist[j1]){dist[j1] = newdist;prev[j1] = u;}}}}}//输出最短路径v源点，i终点void Traceback(int v,int i,int prev[]){if(v == i){cout<<i;fout<<i;return;}Traceback(v,prev[i],prev);cout<<"->"<<i;fout<<"->"<<i;}结果：#include <iostream>#include <limits>#include <fstream>#include <string>using namespace std;ofstream fout("e://dijkstra-output2.txt");struct Node { //定义表结点int adjvex; //该边所指向的顶点的位置int weight;// 边的权值Node *next; //下一条边的指针};struct HeadNode{ // 定义头结点int nodeName; // 顶点信息int inDegree; // 入度int d; //表示当前情况下起始顶点至该顶点的最短路径,初始化为无穷大bool isKnown; //表示起始顶点至该顶点的最短路径是否已知,true表示已知，false表示未知int parent; //表示最短路径的上一个顶点Node *link; //指向第一条依附该顶点的边的指针};//G表示指向头结点数组的第一个结点的指针//nodeNum表示结点个数//arcNum表示边的个数void createGraph(HeadNode *G, int nodeNum, int arcNum) {cout << "开始创建图(" << nodeNum << ", " << arcNum << ")" << endl; //初始化头结点for (int i = 0; i < nodeNum; i++) {G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推G[i].inDegree = 0; //入度为0G[i].link = NULL;}inta[6][6]={{0,999,15,999,999,999},{2,999,999,999,10,30},{999,4,0,999,99 9,10},{999,999,999,0,999,999},{999,999,999,15,0,999},{999,999,999,4,1 0,0}};for (int j = 0;j<6;j++) {for(int k=0;k<6;k++){int begin, end, weight;begin = j+1;end=k+1;weight= a[j][k];// 创建新的结点插入链接表Node *node = new Node;node->adjvex = end - 1;node->weight = weight;++G[end-1].inDegree; //入度加1//插入链接表的第一个位置node->next = G[begin-1].link;G[begin-1].link = node;}}}void printGraph(HeadNode *G, int nodeNum) {for (int i = 0; i < nodeNum; i++) {cout << "结点v" << G[i].nodeName << "的入度为";cout << G[i].inDegree << ", 以它为起始顶点的边为: ";Node *node = G[i].link;while (node != NULL) {cout << "v" << G[node->adjvex].nodeName << "(权:" << node->weight << ")" << " ";node = node->next;}cout << endl;}}//得到begin->end权重int getWeight(HeadNode *G, int begin, int end) {Node *node = G[begin-1].link;while (node) {if (node->adjvex == end - 1) {return node->weight;}node = node->next;}}//从start开始，计算其到每一个顶点的最短路径void Dijkstra(HeadNode *G, int nodeNum, int start) {//初始化所有结点for (int i = 0; i < nodeNum; i++) {G[i].d = INT_MAX; //到每一个顶点的距离初始化为无穷大G[i].isKnown = false; // 到每一个顶点的距离为未知数}G[start-1].d = 0; //到其本身的距离为0G[start-1].parent = -1; //表示该结点是起始结点while(true) {//==== 如果所有的结点的最短距离都已知, 那么就跳出循环int k;bool ok = true; //表示是否全部okfor (k = 0; k < nodeNum; k++) {//只要有一个顶点的最短路径未知,ok就设置为falseif (!G[k].isKnown) {ok = false;break;}}if (ok) return;//==========================================//==== 搜索未知结点中d最小的,将其变为known//==== 这里其实可以用最小堆来实现int i;int minIndex = -1;for (i = 0; i < nodeNum; i++) {if (!G[i].isKnown) {if (minIndex == -1)minIndex = i;else if (G[minIndex].d > G[i].d)minIndex = i;}}//===========================================cout << "当前选中的结点为: v" << (minIndex+1) << endl;G[minIndex].isKnown = true; //将其加入最短路径已知的顶点集// 将以minIndex为起始顶点的所有的d更新Node *node = G[minIndex].link;while (node != NULL) {int begin = minIndex + 1;int end = node->adjvex + 1;int weight = getWeight(G, begin, end);if (G[minIndex].d + weight < G[end-1].d) {G[end-1].d = G[minIndex].d + weight;G[end-1].parent = minIndex; //记录最短路径的上一个结点}node = node->next;}}}//打印到end-1的最短路径void printPath(HeadNode *G, int end) {if (G[end-1].parent == -1) {cout << "v" << end;fout << "v" << end;} else if (end != 0) {printPath(G, G[end-1].parent + 1); // 因为这里的parent表示的是下标，从0开始，所以要加1cout << " -> v" << end;fout << " -> v" << end;}}int main() {HeadNode *G;int nodeNum, arcNum;nodeNum=6;arcNum=36;G = new HeadNode[nodeNum];createGraph(G, nodeNum, arcNum);cout << "=============================" << endl;cout << "下面开始打印图信息..." << endl;printGraph(G, nodeNum);cout << "=============================" << endl;cout << "下面开始运行dijkstra算法..." << endl;for (int i=1;i<=6;i++){Dijkstra(G, nodeNum, i);cout << "=============================" << endl;cout << "打印从v"<<i<<"开始所有的最短路径" << endl;fout << "打印从v"<<i<<"开始所有的最短路径" << endl;for (int k = 1; k <= nodeNum; k++) {if(k!=i){if(G[k-1].d>=150){cout<<"v"<<i<<"到v" << k << "无法到达！";fout<<"v"<<i<<"到v" << k << "无法到达！";}else{cout << "v"<<i<<"到v" << k << "的最短路径为" << G[k-1].d << ": "; fout << "v"<<i<<"到v" << k << "的最短路径为" << G[k-1].d << ": "; printPath(G, k);}cout << endl;fout << endl;}}}}算法分析：图中应用Dijkstra算法更好地实现最短路问题，效率提高很多。