如果你要从一个城市到另一个城市，中途可以有很多种换乘方法，根据不同人的需求，怎么样才能实现价格最少（价格和路程成正比）？怎么样能实现换乘次数最少？
有很多种可能的情况，这时候怎么样找到合适的方案呢？
这就需要研究图的最短路径问题。
不过在网图和非网图中，最短路径的含义不一样。因为非网图的边上没有权值，它的最短路径就是经过边数最少的情况；而对于网图来说，最短路径指的是两顶点间经过的边上的权值之和的最小路径，并且路径上的第一个点被称为源点，最后一个点被称为终点。
Dijkstra 算法：这是一个按路径长度依次递增的次序产生最短路径的算法。它并不是一下子就求出一个点到另一个点的最短路径，而是一步步求出他们之间顶点的最短庐江，过程中都是基于已经求出的最短路径求出的最短路径，最终得到你想要的结果，其时间复杂度为 O(）。
这么说可能有点难懂，先看例题：
如果已知一个网状图，求从 V0 点到其他点的最短路径。
输入
第一行输入两个数 n，m，分别代表顶点数和边数；
第 m+1 行，每行三个数 x，y，z，代表一条边的信息（两个端点和它的权值）
输出
一行数字，一共 n 个数，每个数字代表 V0 到该点的最短路径
样例输入
9 16
0 1 1
0 2 5
1 2 3
1 3 7
1 4 5
2 4 1
2 5 7
3 4 2
5 4 3
3 6 3
4 6 6
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4
样例输出
0 1 4 7 5 8 10 12 16
解题思路
用邻接二维矩阵 a 存储边的信息；
数组 D 临时存储当前最短路径；
数组 P 存放最短路径走过最后一个的下标（比如最短路径是 1->2->3->4，那么 P[4]=3）；
数组 final 记录是否找到最短路径；
首先将每个端点与 v0 的距离存放在 D 数组中，比较得到一个最小值 min，记录下它的下标 k，将 final[k] 赋值为 1，避免重复，然后通过这个下标找是否存在 a[k][w]+min<D[w]，满足条件就更新，接着将 k 存入 P[w].
代码如下：
#include<stdio.h>
int a[1000][1000];//邻接矩阵
int D[1000];//临时存储当前最短路径
int P[1000];//存放最短路径走过最后一个的下标（比如最短路径是 1->2->3->4，那么 P[4]=3）
int final[1000];//初始化是 0，当下标对应的值为 1时，说明已经求得最短路径
int n,m;
void shortestPath_Dijkstra()
{
int min,v,w,i,j,k;
for(i=0;i<n;i++)
{
final[i]=0;//初始化为零，此时所有的点都未加入路径
D[i]=a[0][i];//将 v0与其他边的权值存入 D数组
P[i]=-1;//将 P数组初始化
}
D[0]=0;//将 v0到 v0的最短路径赋为 0
final[0]=1;//v0的最短路径找到了，将 final数组的值赋为 1
for(v=1;v<n;v++)//从 v1开始循环
{
min=99999999;//将 min赋为一个较大值
for(w=1;w<n;w++)
{
if(final[w]!=1&&min>D[w])//找到临时数组中的最小值且该点没有被找到过
{
min=D[w];//更新
k=w;
}
}
final[k]=1;//找过后要将 final赋值为 1，避免重复
for(w=1;w<n;w++)
{
while(final[w]!=1&&D[w]>min+a[k][w])//min+a[k][w]——该点先前求出的（v0至 vk）最短路径（min）加上 vk与 vw连线的和
{
D[w]=min+a[k][w];//更新
P[w]=k;
}
}
}
}
int main()
{
int i,j;
int x,y,z;
scanf("%d %d",&n,&m);//输入顶点数和边数
for(i=0;i<n;i++)//将邻接二维矩阵中的值初始化为一个较大值
{
for(j=0;j<n;j++)
a[i][j]=99999999;
}
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
a[x][y]=z;//无向图，两个端点可以双向通过，在邻接矩阵要存两次
a[y][x]=z;
}
shortestPath_Dijkstra();//进入函数
for(i=0;i<n;i++)//输出找到的各端点到 v0的最短路径
printf("%d ",D[i]);
return 0;
}