数据结构小学期-算法演示程序实验报告(5)

石家庄铁道大学实习报告

}

cout << \已知最短路径的结点为: v\ G[minIndex].isKnown = true; //将其加入最短路径已知的顶点集

D_Node *node = G[minIndex].link; // 将以minIndex为起始顶点的所有的d更新 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 << \ } else if (end != 0) {

printPath(G, G[end-1].parent + 1); // 因为这里的parent表示的是下标，从0开始，所以要加1

cout << \ } }

//调用迪杰斯特拉的相关代码 void show_Dijkstra() {

HeadNode *G; //头结点

int nodeNum, arcNum; //顶点个数，边的个数 cout << \请输入顶点个数，边的个数: \ cin >> nodeNum >> arcNum;

G = new HeadNode[nodeNum];

createGraph(G, nodeNum, arcNum); //创建图 cout << \ cout << \下面开始打印图信息...\

printGraph(G, nodeNum); //打印图 cout << \ cout << \下面开始运行dijkstra算法...\

Dijkstra(G, nodeNum, 1); //运行Dijkstra算法 cout << \ cout << \打印从v1开始所有的最短路径\ for (int k = 2; k <= nodeNum; k++) {

cout << \到v\的最短路径为\

21 / 22

石家庄铁道大学实习报告

printPath(G, k); //打印最短路径 cout << endl; } }

//------------------------------------------Dijkstra算法结束

---------------------------------------------------------------// //菜单

void menu(){

cout<<\欢迎来到算法演示程序****************************************\

cout<<\算法 2.Kruskal算法\ cout<<\算法 4.Dijkstra算法\

cout<<\退出\}

void main(){

menu();int i; while(1){

cout<<\请选择您的操作：\ switch(i){

case 1:cout<<\接下来运行Prim算法...\

case 2:cout<<\接下来运行Kruskal算法...\ case 3:cout<<\接下来运行Floyd算法...\

case 4:cout<<\接下来运行Dijkstra算法...\ case 5:cout<<\退出成功，欢迎下次登录。。。\ default:cout<<\输入错误。\

} //switch结束 if(i!=5)continue; else break;

} //while循环结束 }

22 / 22