---

數(shù)據(jù)結(jié)構(gòu)—多源最短路徑

---

原理：參考趣學數(shù)據(jù)結(jié)構(gòu)

代碼：

棧代碼：

#pragma once #include<stdio.h> #define maxSize 100 typedef struct stack {int * base;int * top; }stack; bool init(stack & Stack) {//棧的初始化Stack.base = new int[maxSize];if (!Stack.base) {return false;}Stack.top = Stack.base;return true; } bool push(stack & Stack,int e) {//入棧if (Stack.top - Stack.base == maxSize) {//滿棧，不能再插入return false;}*(Stack.top) = e;Stack.top++;return true; } bool pop(stack & Stack, int &e) {//出棧if (Stack.base == Stack.top) {//棧空return false;}Stack.top--;e = *(Stack.top);return true; } int getTop(stack &Stack) {if (Stack.base == Stack.top) {//棧空return -1;}return *(Stack.top - 1); } void printStack(stack Stack) {//遍歷棧中的元素while (Stack.base != Stack.top) {printf("%d ", *(Stack.top - 1));Stack.top--;} } bool empty(stack Stack) {//棧空的判斷if (Stack.base == Stack.top) {return true;}return false; } void testStack() {//測試棧是否有問題stack Stack;init(Stack);int value;while (1) {scanf_s("%d", &value);if (value == -1) {break;}push(Stack, value);}printStack(Stack); }

---

多源最短路徑代碼：

---

#include<stdio.h> #include<stdlib.h> #include"stack.h" #define N 100 #define elemType int //const int MAX_INT = (1 << 31) - 1; //const int MAX_INT = 0X7fffffff; #define INF (((unsigned int)(-1)) >> 1) typedef struct GraphMatrix {elemType vNode[N][N];int vNum, eNum; }GraphMatrix; void findPath(GraphMatrix G, int dist[N][N], int p[N][N],stack &Stack);//聲明 void initGMaxtix(GraphMatrix &G) {//初始化鄰接矩陣printf("輸入頂點數(shù)和邊數(shù)\n");scanf_s("%d%d", &G.vNum, &G.eNum);for (int i = 0; i < G.vNum; i++) {//初始化鄰接矩陣for (int j = 0; j < G.vNum; j++) {G.vNode[i][j]= INF;}}printf("輸入頂點v1到頂點v2和其邊的權(quán)重\n");for (int i = 0; i < G.eNum; i++) {int v1, v2, weights;scanf_s("%d%d%d", &v1, &v2, &weights);G.vNode[v1][v2] = weights;} } void print10(GraphMatrix G) {printf("鄰接矩陣如下:\n");for (int i = 0; i < G.vNum; i++) {for (int j = 0; j < G.vNum; j++) {printf("%d ", G.vNode[i][j]);}printf("\n");} } void print101(int result[N][N], int length) {for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {printf("%d ", result[i][j]);}printf("\n");}printf("\n"); } void Floyd(GraphMatrix G) {//多源最短路徑求解int dist[N][N], p[N][N];//分別為多源點到其他點的距離和這段距離所經(jīng)過的那些頂點的記錄數(shù)組pfor (int i = 0; i < G.vNum; i++) {for (int j = 0; j < G.vNum; j++) {dist[i][j] = G.vNode[i][j];if (G.vNode[i][j] == INF || i==j ) {//對距離數(shù)組和記錄數(shù)組初始化p[i][j] = -1;}else {p[i][j] = i;}}}for(int k=0;k<G.vNum;k++){for (int i = 0; i < G.vNum; i++) {//更新距離數(shù)組for (int j = 0; j < G.vNum; j++) {//注意INF+INF越界問題 如果沒有發(fā)現(xiàn)多調(diào)試if (dist[i][k]<INF && dist[k][j]<INF && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];p[i][j] = p[k][j];}}}}//print101(dist, G.vNum);stack Stack;init(Stack);printf("輸出多源最短路徑的最優(yōu)方案\n");findPath(G, dist, p,Stack); } void findPath(GraphMatrix G, int dist[N][N], int p[N][N], stack &Stack) {for (int i = 0; i < G.vNum; i++) {for (int j = 0; j < G.vNum; j++) {if (p[i][j] == -1) {//起點到起點printf("%d---%d不可達!\n", i, j);continue;}push(Stack, j);int x = p[i][j];while (x != -1) {//入棧查找路徑push(Stack, x);x = p[i][x];}int e;while (!empty(Stack)) {//出棧遍歷路徑printf("%d", getTop(Stack));pop(Stack, e);if (Stack.top - Stack.base >= 1) {printf("---");}}printf(" 這段路徑的距離為:%d\n", dist[i][j]);}} } int main() {GraphMatrix G;initGMaxtix(G);print10(G);printf("\n");Floyd(G);system("pause");return 0; }

測試截圖：

時間復雜度為O(n x n x n)，空間復雜度為O(n x n)

如果存在什么問題，歡迎批評指正！謝謝！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的数据结构---多源最短路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。