如何让计算机来帮我们计算一条从一个地点到其他所有地点的最短路线呢？今天我们就来讨论这个问题。这个问题的核心就是求图中一个顶点到其他顶点的最短路径，也就是从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径。
算法基本思想：把图中顶点集合V分成两组，令S表示已经求出最短路径的顶点集合，其余尚未确定最短路径的顶点集合为第二组。按最短路径长度的递增次序逐个地把第二组的顶点加入S中，直至从v出发可以到达的所有顶点都在S中。在这过程中，总保持从v到S中各顶点的最短路径长度都不大于从v到第二组的任何顶点的最短路径长度。另外，每个顶点对应一个距离，S中顶点的距离是从v到此顶点的最短路径长度，第二组顶点的距离是从v到此顶点的只包含S中的顶点为中间顶点的当前最短路径长度。 假设我们要求出顶点v到图中其他顶点的最短路径。首先，对于给定的有向图，我们需要二维数组G来存储顶点之间边的关系。其中若从顶点i到顶点k存在一条权值为a的路径，我们就将矩阵中（i，k）中的内容置为a，若没有，我们就将矩阵中（i，k）的内容置为∞（在程序中我们用9999来表示），同时，所有（i，i）这样的点的内容置为0.其次，我们还需要一个dist数组来存储v号顶点到其余顶点的当前距离，一旦从源点v到顶点k的最短路径已求出，dist[k]就是从原点v到顶点k的最短路径长度。最后，为了记录最短路径，我们还使用了数组pre，数组元素pre[j]存放从源点v到顶点j的最短路径中j前面的顶点。有了pre数组，我们就能够很容易地求得从源点v到其他各个顶点的路径。
基本步骤如下：
（1）把顶点v放入集合S中
（2）按如下步骤逐个求得从v到其他顶点的最短路径，直至把所有顶点的最短路径求出
A. 在dist数组中选取不在S中，且具有最小距离的顶点k
B. 把顶点k加入集合S中
C. 修改不在S中的顶点的距离，也就是需要看看新加入的顶点k是否可以 到达其他顶点，看看通过该顶点k到达其他点的路径长度是否比源点 直接到达短，如果是，那么就替换这些顶点在dis中的值。
#include
#include
#define MAXINT 9999999
#define MAXN 1000
typedef int MAT[MAXN][MAXN];
MAT cost,a,path;
int dist[MAXN],pre[MAXN],n,v;
int init()//初始化邻接矩阵
{
int j1,i,m,n,u,v1,w;
scanf("%d%d",&n,&m);//输入结点数，边数
for(i = 0;i <= n; i++)//初始化邻接矩阵
{
for(j1 = 0;j1 <= n;j1 ++)
{
cost[i][j1]=MAXINT;
}
}
for(i=0;i<=n;i++)
{
cost[i][i]=0;
}
for(i = 0;i < m; i++)
{
scanf(" %d%d%d ",&u, &vl, &m);//依次输入每个边的两个端点，权值
cost[u][v1]=w;
}
return n;
}
void shortestpath(MAT cost,int n,int v,int dist[],int pre[])//Dijkstra,v
{
int s[MAXN],i,j,k,min,x=1,n1;
int road[MAXN];
for(i=1;i<=n;i++)
{
dist[i]=cost[v][i];//dist数组赋初值
s[i]=0;
if(dist[i] < MAXINT)//如果v和i中有一条边，则pre[i]=v
pre[i]=v;
else
pre[i]=0;//如果没有边，则pre[i]=0
}
s[v]=1;//起始顶点
pre[v]=0;
for(i = 1;i <= n; i++)
{
min=MAXINT;
k=0;
for(j = 1;j <= n; j++)//寻找dist[j]的最小值
//{
if(s[j]==0)
{
if(dist[j]!=0 && dist[j] < min)//dist[j]小于当前最小值且不等于0
{
min=dist[j];//最小值
k=j;
}
}
if(k==0) break;//没有与出发点相连的点
//}
s[k]=1;//把找到的k加在集合s中
for( j=1 ; j<=n ;j++)//修改不在s中的顶点的距离
{
if(s[j]==0 && cost[k][j] < MAXINT)//j不在s中并且k到j有边
{
if(dist[k]+cost[k][j] < dist[j])//若找到更短的路径
{
dist[j]=dist[k]+cost[k][j];//修改最短路径
pre[j]=k;
}
}
}
}
if(dist[n]!=MAXINT)//若有路径
{
printf("%d\n",dist[n]);//输出最短路径权值
road[0]=n;//road标记路径，road[0]为路径的终点
n1=n;
while(n1!=v)//从路径的终点向前逐步找出路径
{
road[x++]=pre[n1];//找到前一个结点存贮在数组中
n1=pre[n1];
}
road[x]=v;
for(i = x-1; i > 0; i--)
{
printf("%d->",road[i]);//从后向前输出数组中的结点，即为路径
}
printf("%d\n",road[0]);
}
else
printf("-1\n");
}