最短路徑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++易錯的地方