最短路径C/C++

2019-11-06 07:37:40

字体：大中小

来源：转载

供稿：网友

最短路径

本文介绍求最短路径，但不是Dijkstra算法和Bellman-ford算法求有向图中一点到其余各点的最短路径，而是求解有向图中指定两点的最短路径。方法很简单，建立与BFS之上，因此我们只需要修改队列中的内容。这里本来该有图的，但是最近忙专业课，下回补上！typedef struct QNode{ int pos; //由于输入的定点数为char型，因此我们需要用转化为在vex[]数组中的位置 VertexType data; struct QNode *PRior; //指向之前出队列的元素。 struct QNode *next;}QNode;具体算法如下：（PS：最后输出的答案是反向的，可以利用一个栈或者数组反向输出都行）#include <iostream>#include <malloc.h>using namespace std;#define VRType int#define VertexType char#define MAX_VERTEX_NUM 30typedef struct{ VertexType vexs[MAX_VERTEX_NUM]; VRType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum,arcnum;}MGraph;void CreatMGraph(MGraph &G){ cin>>G.vexnum; for(int i = 0; i < G.vexnum; i++) cin>>G.vexs[i]; for(i = 0; i < G.vexnum; i++) for(int j = 0; j < G.vexnum; j++) cin>>G.edges[i][j];}typedef struct QNode{ int pos; VertexType data; struct QNode *prior; struct QNode *next;}QNode;typedef struct{ QNode *front; QNode *rear;}LiQueue;void InitQueue(LiQueue *&Q){ Q = (LiQueue *) malloc (sizeof(LiQueue)); Q->front = Q->rear = NULL;}bool EmptyQueue(LiQueue *Q){ if((!Q->front) || (!Q->rear)) return true; else return false;}void EnQueue(LiQueue *&Q, MGraph G, int n, QNode *q) //n表示该点的在vex[]数组中的位置{ //q表示是刚出队列的指针 QNode *p; p=(QNode *) malloc (sizeof(QNode)); p->data = G.vexs[n]; p->pos = n; p->prior = q; p->next = NULL; if(EmptyQueue(Q)) Q->front = Q->rear = p; else{ Q->rear->next = p; Q->rear = p; }}void DeQueue(LiQueue *&Q, QNode *&p){ if(!EmptyQueue(Q)){ p = Q->front; Q->front = Q->front->next; }}int visit[MAX_VERTEX_NUM]={0};void ShortestPath(MGraph G,VertexType start,VertexType end){ LiQueue *Q; QNode *p; InitQueue(Q); for(int i = 0; i < G.vexnum; i++) if(G.vexs[i] == start) break; EnQueue(Q, G, i, NULL); //由于队列空，因此将NULL传给指针q visit[i] = 1; while(!EmptyQueue(Q)){ DeQueue(Q,p); //指针p接受了出队列的队列元素 if(p->data == end) //如果找到就跳出循环 break; for(i = 0; i < G.vexnum; i++) if(G.edges[p->pos][i] && !visit[i]){ visit[i] = 1; EnQueue(Q, G, i, p); //这里将p传给q } } while(p){ //这时p指向的就是终点元素end，则依次寻找前驱元素输出，所以答案是反的 cout<<p->data; p = p->prior; } cout<<endl;}int main(){ char start,end; MGraph g; CreatMGraph(g); cin>>start>>end; ShortestPath(g,start,end); return 0;}

上一篇：C++利用递归求排列的代码

下一篇：c++易错的地方