一：前言

本次題解先展示用鄰接矩陣做的，但其會出現內存超限，因為確實是臨界矩陣在數據很大的時候相比臨界表是耗內存的，但是以前習慣用臨界矩陣了，所以一上來就用臨界矩陣做了，后來上網查了后知道鄰接矩陣會內存超限，所以后來又用鄰接表寫了一遍。

二：題目

請編寫程序求給定正權有向圖的單源最短路徑長度。圖中包含n個頂點，編號為0至n-1，以頂點0作為源點。

輸入格式:
輸入第一行為兩個正整數n和e，分別表示圖的頂點數和邊數，其中n不超過20000，e不超過1000。接下來e行表示每條邊的信息，每行為3個非負整數a、b、c，其中a和b表示該邊的端點編號，c表示權值。各邊并非按端點編號順序排列。

輸出格式:
輸出為一行整數，為按頂點編號順序排列的源點0到各頂點的最短路徑長度（不含源點到源點），每個整數后一個空格。如源點到某頂點無最短路徑，則不輸出該條路徑長度。

輸入樣例:

4 4 0 1 1 0 3 1 1 3 1 2 0 1

輸出樣例:

1 1

三：介紹dijkstra算法

1.dijkstra

無論你用哪種數據結構存儲數據，其算法思想是一樣的，dijkstra算法，單源點最短路徑，其在更新的階段體現了貪心，每次都找最優的結，即最小的路徑

2：做題思路

思路：1.首先讀題分析到 這是一個有向圖
2.單源點最短路徑：確定一個點為源點，其到其他點的最短路徑；本題當中
因為是有向圖，當沒有最短路徑就不輸出了

分析：示例： 4 4
0 1 1
0 3 1
1 3 1
2 0 1

輸出為： 1 1

這是0 到 1 的最短路徑和0到3的最短路徑 而 0到 2無路徑 （2到0有路徑）
3.本題我先用的是臨界矩陣儲存數據的會出現內存超限后來改為鄰接表，而體現貪心的部分是代碼中的更新的部分，每次都找最優解
4.具體代碼流程需要自己分析示例圖解：這里有我分析的無向圖的圖解，思路和有向圖類似
懂了這個就懂了本題的寫碼思路了

3.圖示（以無向圖為例，和有向圖思路是一致的）

四：上碼

1.用鄰接矩陣存儲的數據（會出現內存超限）

/**思路：1.首先讀題分析到 這是一個有向圖2.單源點最短路徑：確定一個點為源點，其到其他點的最短路徑；本題當中因為是有向圖，當沒有最短路徑就不輸出了分析：示例： 4 40 1 10 3 11 3 12 0 1 輸出為： 1 1 這是0 到 1 的最短路徑和0到3的最短路徑 而 0到 2無路徑 （2到0有路徑） 3.本題我用的是臨界矩陣儲存數據的，而體現貪心的部分是代碼中的更新的部分，每次都找最優解 4.具體代碼流程需要自己分析示例圖解：這里有我分析的無向圖的圖解，思路和有向圖類似懂了這個就懂了本題的寫碼思路了 */ #include<bits/stdc++.h>using namespace std;typedef struct Graph * PtrGraph; typedef struct Graph{int Nv;int Ne;int Date[2276][2274];} graph;int infinite = 99999;//初始化臨界矩陣void CreateGraph(PtrGraph G){cin >> G->Nv >> G->Ne;//初始化臨界矩陣 for(int i = 0; i < G->Nv; i++){for(int j = 0; j < G->Nv; j++){if(i == j){G->Date[i][j] = 0;} else{G->Date[i][j] = infinite;//當兩個點不相連的時候為無窮大 }} }//向臨界矩陣中賦值for(int k = 0; k < G->Ne; k++){int i,j,w;cin >> i >> j >> w;G->Date[i][j] = w;//這里體現有向圖，即從 i 到 j 在臨界矩陣中有值，而從j到i無值 } } //驗證輸出臨界矩陣 // void print_Graph(PtrGraph G) {// for(int i = 0; i < G->Nv; i++){// for(int j = 0; j < G->Nv; j++){// cout << G->Date[i][j] << ' ';// } // cout << endl;// }// }//核心代碼 體現貪心的代碼 每次更新均找距離最短的點 void dijkstra(PtrGraph G){int dist[2001];//用于存儲源點到各個點的最短距離int visited[2001];//用于記錄已經訪問了哪個點的 for(int i = 0; i < G->Nv; i++){dist[i] = G->Date[0][i];//題目給出了源點是 0 } visited[0] = 1;//表示1已經訪問過了//更新 while(1){int m = -1;int min = infinite;for(int i = 0; i < G->Nv; i++){if(visited[i] != 1 && dist[i] < min){min = dist[i];m = i; } } if(m == -1){//如果m無變化,說明圖中的各點已經更新完了 break;}visited[m] = 1;for(int i = 0; i < G->Nv; i++){if(visited[i] != 1 && min + G->Date[m][i] < dist[i]){//這里注意 min + G->Date[m][i]：//表示了一個源點到其最短的距離（min）的點，//然后需要判斷這個點到其他點的距離加上min和源點到其他點的距離進行比較更新dist[i] = min + G->Date[m][i];}} } for(int i = 1; i < G->Nv; i++){if(dist[i] == infinite)continue;else{cout << dist[i] << ' '; } } } int main(){PtrGraph G = (PtrGraph)malloc(sizeof(struct Graph));CreateGraph(G);// print_Graph(G);dijkstra(G);}

2：用鄰接表存的正確結果

#include<bits/stdc++.h> using namespace std; #define max 20001struct Node{int to;//指向邊的結點 int val;//邊的權值 int next;//指向下一個結點的下標 } node[max];int head[max],n,m,num = 0; int infinite = 99999;//建立鄰接表 void add(int from,int to,int val){num++;node[num].to = to;node[num].val = val;node[num].next = head[from];head[from] = num;//更新head的值，當再有從from連接的點 它的下一個為 num 坐標 } //dij算法 void dijkstra(){int dist[max];fill(dist, dist + 20001, infinite);int vis[max] = {0};for(int i = head[0]; i != 0; i = node[i].next){//這里是選取源點為0的頂點，將和其相連邊的權值存進去了 dist[node[i].to] = node[i].val; //比如：0到1：即 node[i].to = 1表示的是頂點, node[i].val = 1 表示0到1這條邊的權值為1;dist[1] = 1}vis[0] = 1;while(1){int m = -1;int min = infinite;for(int i = 0; i < n; i++){if(vis[i] != 1 && dist[i] < min){min = dist[i];m = i;}}if(m == -1){//已經遍歷完了所有結點 break;}vis[m] = 1;//確定m這個頂點 接下來遍歷 m這個結點的鏈表 for(int i = head[m]; i != 0; i = node[i].next){if(vis[node[i].to] != 1 && min + node[i].val < dist[node[i].to]){//vis[node[i].to] != 1如果出現 1到2 和2到1這種情況，那么當1已經遍歷過，在頂點為2的這個鏈表中就不用再遍歷了dist[node[i].to] = min + node[i].val;} } } for(int i = 0; i < n; i++){if(dist[i] != infinite){cout << dist[i] << ' ';}} } int main(){memset(head,0,sizeof(head));cin >> n >> m;for(int i = 0; i < m; i++){int from,to,val;cin >> from >> to >> val;add(from,to,val);} //測試鄰接表的數據是否正確 // for(int i = 0; i < n; i++){ // cout << i << ' '; // for(int j = head[i]; j != 0; j = node[j].next){ // cout << node[j].to << ' ' << node[j].val << ' '; // } // cout << endl; // }dijkstra();}//4 4 //0 1 1 //0 3 1 //1 3 1 //2 0 1//鄰接表輸出的數據 //0 3 1 1 1 //1 3 1 //2 0 1 //3//4 5 //0 1 1 //1 3 2 //0 3 4 //0 2 2 //2 3 3

五：知識速遞（如果兄弟們對鄰接表不熟悉，可以學習下哈）

鄰接表的用法

加油 兄弟們！！！

總結

以上是生活随笔為你收集整理的7-2 单源最短路径 (10 分)(思路+详解+邻接表做法)Come Brather!!!!!!!!!!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。