dijkstra算法：

求指定两点间的距离（不适用负边权），O(n^2)

#include<iostream>  
#include<vector>  
#include<cstdio>  
using namespace std;
const int INF = 0x3fffffff;
const int MAXV = 105;
int map[MAXV][MAXV], d[MAXV];//map存地图，d存到此点的最短路径   
bool vis[MAXV];//存是否访问过   
//int pre[MAXV];//pre[k]表示从起点到顶点k的最短路径上k的前一个顶点   
//int c[MAXV],cost[MAXV][MAXV];//新增边权 ,边权最小   
//int w[MAXV],weight[MAXV];//新增点权 ,w从起点到此点的最大点权 ，点权最大   
//int num[MAXV]; //求最短路径条数   
void dijkstra(int n, int s)//n为总点数，s为起点   
{
	fill(vis, vis + MAXV, false);
	fill(d, d + MAXV, INF);//初始化为最大   
//  fill(c, c + MAXV, INF);  
  //memset(num,0,sizeof(num));  
  //memset(w,0,sizeof(w));   
	d[s] = 0;//起点初始化为0   
  //c[s]=0;  
  //w[s]=weight[s];  
  //num[s]=1; //第一个点为 1，别的全为0   
	for (int i = 0; i < n; i++)//遍历每个点   
	{
		int u = -1, Min = INF;//u使d[u]最小，Min存最小的d[u]   
		for (int j = 1; j <= n; j++)//寻找未访问点中最小的   
		{
			if (vis[j] == false && d[j] < Min)//寻找最小的点   
			{
				u = j;
				Min = d[j];
			}
		}
		if (u == -1)return;//不连通，返回   
		vis[u] = true;//标记为已访问   
		for (int k = 1; k <= n; k++)//更新与u点相连接点的最优解   
		{
			//k未访问&&以u为中介点可以使d[k]更优   
			if (vis[k] == false && map[u][k] != INF)
			{
				if (d[u] + map[u][k] < d[k])//如果是更优解   
				{
					d[k] = d[u] + map[u][k];
					//pre[k]=u;//存前面的点   
					//c[k]=c[u]+cost[u][k];
					//w[k] = w[u] + weight[k];  
					//num[k] = num[u];  
				}
			/*else if(d[u] + map[u][k] == d[k])//如有第二权值，且需求路径，更新第二权值时更新路径
			{
			if(w[u]+weight[k]>w[k])//最短距离相同时能使w[k]更优
			{
			w[k]=w[u]+weight[k];
			//pre[k]=u;
			}
			if(c[u]+cost[u][k]<c[k])//最短距离相同时能使c[k]更优
			{
			c[k]=c[u]+cost[u][k];
			//pre[k]=u;
			}
			num[k]+=num[u];//最短距离相同时累加num
			}
			*/
			}
		}
	}
}
/*void dfs(int s,int v)//最短路径只有一条时，输出最短路径
{
if(v==s)
{
printf("%d\n",s);
return;
}
dfs(s,pre[v]);
printf("%d\n",v);
}*/
int main()
{
	int i, x, y, z, n, m, s, t;//n为总点数，m为输入路径数   
	while (scanf("%d %d",&n,&m)!=EOF&&m&&n)
	{
		fill(map[0], map[0] + MAXV*MAXV, INF);//初始化map   
		for (i = 1; i <= m; i++)
		{
			scanf("%d %d %d",&x,&y,&z);
			if (map[x][y]>z)//防重边   
				map[x][y] = map[y][x] = z;//无向边   
		}
		s = 1;//起点
		dijkstra(n,s);//s起点为1   
		t = n;//t为终点
		cout << d[t] << endl;//输出终点的最短路径   
	}
	return 0;
}

floyd算法：

可以求出任意两点间的最短距离，O（n^3）

#include<iostream>
#include<cstdio>
using namespace std;
const int INF = 0x3fffffff;
const int MAXV = 1005;
int map[MAXV][MAXV];//map存地图
void floyd(int n)
{
	for(int i=1;i<=n;i++)map[i][i]=0; //i到i点初始化为0 
	for(int k=1;k<=n;k++)//找出一个中介点 使map[i][j]更优 
	{
		for(int i=1;i<=n;i++)
		{
			if(map[i][k]==INF)continue;//不连通 
			for(int j=1;j<=n;j++)
			if(map[k][j]!=INF&&map[i][k]+map[k][j]<map[i][j])//若通过此点更优 
			map[i][j]=map[j][i]=map[i][k]+map[k][j];
		}
	}
}
int main()
{
	int i, x, y, z, n, m, s, t;//n为总点数，m为输入路径数   
	while (scanf("%d %d",&n,&m)!=EOF&&m&&n)
	{
		fill(map[0], map[0] + MAXV*MAXV, INF);//初始化map  
		for (i = 1; i <= m; i++)
		{
			scanf("%d %d %d",&x,&y,&z);
			if (map[x][y]>z)//防重边 
				map[x][y] = map[y][x] = z;//无向边   
		}   
		floyd(n);
		s=1;//起点 
		t=n;//终点 
		cout << map[s][t] << endl;//输出任意两点的最短路径   
	}
	return 0;
 }

spfa算法

可用于有负边权

#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3fffffff;
const int MAXV = 1005;
struct node
{
	int v, dis;//v为目标顶点，dis为边权 
};
vector<node> adj[MAXV];//图的邻接表 
int n, m, d[MAXV], num[MAXV];//d存到此点的最短路径，num记录顶点入队的次数 
bool inq[MAXV];//顶点是否在队列中 
bool spfa(int s)
{
	memset(inq, false, sizeof(inq));
	memset(num, 0, sizeof(num));
	fill(d, d + MAXV, INF);
	queue<int> q;
	q.push(s);//源点入队 
	inq[s] = true;
	num[s]++;//源点入队次数加1 
	d[s] = 0;//源点d值为0 
	while (!q.empty())
	{
		int u = q.front();//队首顶点编号u 
		q.pop();
		inq[u] = false;//设u不在队列 
		for (int j = 0; j<adj[u].size(); j++)//遍历u的所有邻接边v 
		{
			int v = adj[u][j].v;
			int dis = adj[u][j].dis;
			if (d[u] + dis<d[v])//松弛操作 
			{
				d[v] = d[u] + dis;
				if (!inq[v])//如果v不在队列中 
				{
					q.push(v);
					inq[v] = true;
					num[v]++;
					if (num[v] >= n)return false;//有可达负环 
				}
			}
		}
	}
	return true;//无可达负环 
}
int main()
{
	int cost, a, b, s, t;//a点到b点的花费为cost 
	node k;//临时结构体，输入用 
	while (scanf("%d %d", &n, &m) != EOF&&m&&n)
	{
		for (int i = 0; i < MAXV; i++)
			adj[i].clear();
		for (int i = 0; i<m; i++)//m为点数，m为输入的边数 
		{
			scanf("%d %d %d", &a, &b, &cost);
			k.v = b;
			k.dis = cost;
			adj[a].push_back(k);//无向边 
			k.v = a;
			adj[b].push_back(k);
		}
		s = 1;//起点 
		t = n;//终点 
		if (spfa(s))printf("%d\n", d[t]);
		else printf("出现负环，最短路径不存在\n");
	}
}