兩個算法具有相當(dāng)大的相似性，而且都用到了貪心思想，所以把他們放到一起。最短路常用的算法有dijkstra，bellman-ford，floyd。而最小生成樹則是prim和kruskal。下面是各個算法的模板。
Dijkstra:
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define M 1001
5 int map[M][M],dis[M];
6 bool flag[M];
7 void dijkstra(int s,int n,int t) //s是源點，n是點的個數(shù)，t是目的點
8 {
9 int i,j,k,md,temp;
10 for(i=1;i<=n;i++)
11 dis[i]=INF; //初始化將所有dis置為無窮大，源點為0
12 dis[s]=0;
13 memset(flag,false,sizeof(flag)); //開始flag全部為false，表示集合為空
14 for(i=1;i<n;i++){ //進(jìn)行n-1次迭代，每次找出不在集合中的最小邊
15 md=INF;
16 for(j=1;j<=n;j++){
17 if(!flag[j]&&dis[j]<md){
18 md=dis[j];
19 temp=j;
20 }
21 }
22 if(temp==t) break; //如果遇到目的點，可以跳出了
23 flag[temp]=true; //將這個最小邊的點加入集合
24 for(j=1;j<=n;j++){
25 if(!flag[j]&&md+map[temp][j]<dis[j]) //對所有出邊進(jìn)行松弛操作
26 dis[j]=md+map[temp][j];
27 }
28 }
29 }
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
相應(yīng)的最小生成樹的prim模板：
1 #include<iostream>
2 #define INF 0x1f1f1f1f
3 #define M 1000
4 using namespace std;
5 double dis[M],map[M][M];
6 bool flag[M];
7 int prim(int s,int n) //s為起點，n為點的個數(shù)
8 {
9 int i,j,k,temp,md,total=0;
10 for(i=1;i<=n;i++)
11 dis[i]=map[s][i]; //與最短路不同，而是將dis置為map[s][i]
12 memset(flag,false,sizeof(flag));
13 flag[s]=true; //將起點加入集合
14 for(i=1;i<n;i++){ //依舊進(jìn)行n-1次迭代，每次找到不在集合的最小邊
15 md=INF;
16 for(j=1;j<=n;j++){
17 if(!flag[j]&&dis[j]<md){
18 md=dis[j];
19 temp=j;
20 }
21 }
22 flag[temp]=true; //將找到的最小邊的點加入集合
23 total+=md; //并將這個邊的權(quán)值加到total中
24 for(j=1;j<=n;j++) //松弛操作，注意與最短路不同
25 if(!flag[j]&&dis[j]>map[temp][j])
26 dis[j]=map[temp][j];
27 }
28 return total;
29 }
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
下面是最短路的bellmen-ford算法，與dijkstra不同，bellman-ford可以運(yùn)用于有負(fù)權(quán)值的圖，不過復(fù)雜度很高，O(VE )... 慎用~（可以用SPFA，但是那個算法我掌握的不是很好：D）
Bellman-ford算法同樣是對每條邊進(jìn)行N-1次松弛，當(dāng)有權(quán)值為負(fù)時，對所有邊進(jìn)行N-1次松弛，如果dis還能更新，說明有負(fù)環(huán)。
Bellman-ford模板：
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define MAX 102
5 #define MAXM 20008
6
7 int dist[MAX];
8
9 struct Edge{ //邊結(jié)構(gòu)體定義
10 int u, v, w;
11 Edge(){}
12 Edge(int a, int b, int c):u(a), v(b), w(c){}
13 }edge[MAXM];
14
15 int bellman_ford(int n, int m, int s) //n個點、m條邊、s為起點
16 {
17 memset(dist, 0x1f, sizeof(dist)); //初始化距離很大
18 dist[s] = 0;
19 int i, j, u, v, f;
20 for (i = 1; i < n; ++i) //迭代 n - 1 次，對每條邊進(jìn)行n-1次松弛
21 {
22 f = 0;
23 for (j = 0; j < m; ++j)
24 {
25 u = edge[j].u;
26 v = edge[j].v;
27 if (dist[v] > dist[u] + edge[j].w) // 松弛操作
28 {
29 dist[v] = dist[u] + edge[j].w;
30 f = 1;
31 }
32 }
33 if (!f) return 1; //如果其中一次迭代沒改變，停止
34 }
35 for(j = 0; j < m; ++j) //再進(jìn)行一次迭代
36 {
37 u = edge[j].u;
38 v = edge[j].v;
39 if (dist[v] > dist[u] + edge[j].w) //若還能松弛, 則存在負(fù)環(huán)
40 return -1; //存在負(fù)環(huán)返回 -1
41 }
42 return 1; //沒有負(fù)環(huán)返回 1
43 }
算法結(jié)束后dist數(shù)組已經(jīng)是最短路徑。