与最小生成树有些不一样.在这里提出三种算法.
dijkstra算法,是最普通也是最简单的.与prim算法有些类似,但适用范围又不一样,有打印路径和不打印路径的小分法.注意不能用于权值有负的图!!!(而且可以用优先队列优化,可以查一下模板,也比较简单).
首先是不打印路径的dijkstra,类似于DP.(打印单源路径,即某一特定点到其他点的距离)

最近发现一个坑点,初始化地图时最好放在输入前面,然后输入信息时要求小于对应地图的位置时才存入地图中,因为我们要求的是最短路,必须保证地图中是两点的最短距离!!!若之后又输入了某点的信息后距离是比之前的更长的则不能替换的,否则求出来的就不是最短路了.!!!

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxp = 2005;
const int INF= 1000000;
int edge[maxp][maxp];
int near[maxp];
int low[maxp];
int n;

void dijkstra(int u)//从u点开始找出距离所有的点最短距离.
{   memset(low,0,sizeof(low));
    for(int i=0;i<n;i++)
        near[i]=edge[u][i];
    low[u]=1;
    for(int i=0;i<n;i++){
        int minn=INF;
        int v=-1;
        for(int j=0;j<n;j++){
            if(!low[j] && near[j]<minn)
                v=j,minn=near[j];
        }
        low[v]=1;
        for(int j=0;j<n;j++)
            near[j]=min(near[j],edge[v][j]+near[v]);//这样写更简单,不用那个if也行,因为不会影响原先那个最短的.
            //加那个if时间更快点而已,也体现了这个算法不能使用与权值有负的边.
            //如果要打印路径,则这样就不行.好好想想
    }

    for(int i=0;i<n;i++){
        printf("%d ",near[i]);
    }
    printf("\n");
}

int main()//输入哪里怎么改才好输入就是自己的事.
{
    int i,j;
    int u,v,w;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(i==j)  edge[i][j]=0;
            else  edge[i][j]=INF;
        }
    }
    while(1)
    {
        scanf("%d %d %d",&u,&v,&w); //读入边的起点和终点
        if(u==-1 && v==-1 && w==-1) break;
        if(w<edge[u][v])  //这样就可以保证图中存的是两点间的最短距离.
           edge[u][v]=w;   //构造邻接矩阵（这里的输入也说明了它是单向的,既有向）//对应的无向图改成双向的就行了.
    }
    dijkstra(0);//从0开始到所有点的最短距离.(要求那个点,就传那个点进去就行了)
/*--------打印临接矩阵------
    for(int i = 0 ; i <  n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            printf("%6d ",edge[i][j]);
        }
        printf("\n");
    }
--------------------------*/
}

打印路径的.

#include<cstdio>
#include<cstring>
#define INF 1000000 //无穷大
#define maxn 20   //顶点个数的最大值
int n;//顶点个数
int Edge[maxn][maxn];
int s[maxn];
int dist[maxn];
int path[maxn];//因为要打印路径,所以需要一个数组保存这条边来自于那一条边,这样回溯输出便可输出路径.

void dijkstra(int v0)//求v0到其他点的最短路径.
 {  int i,j,k;
    for(i=0;i<n;i++)
    {
        dist[i]=Edge[v0][i];
        s[i]=0;//初始化s数组,用于保存找过的点.
        if(i!=v0 && dist[i]<INF)  path[i]=v0;
        else   path[i]=-1;
    }
    s[v0]=1;//顶点v0加入到顶点集合s中.
    for(int i=1;i<n;i++)
    {   int mini=INF,u=v0;//选择当前集合t中具有最短路径的顶点u；
        for(int j=0;j<n;j++){
            if(!s[j] && dist[j] < mini){  //选择下一次到已知顶点最短的点。
                u=j,mini=dist[j];
            }
        }
        s[u]=1;//将顶点u加入到集合s,表示他的最短路径已求到.
        //修改t集合中顶点dist和path数组元素值.
        for(j=0;j<n;j++){
            if(!s[j] && dist[u] + Edge[u][j] < dist[j]){  //未被标记且比已知的短，可更新
                dist[j]=dist[u] + Edge[u][j] ;
                path[j]=u;
            }
        }
    }
 }

int main()
{
    int i,j;//循环变量.
    int u,v,w;//边的起点与终点及权值.
    scanf("%d",&n);//顶点个数
    for(i=0;i<n;i++){
       for(j=0;j<n;j++){
            if(i==j)  edge[i][j]=0;
            else  edge[i][j]=INF;
        }
    }
    while(1)
    {
        scanf("%d %d %d",&u,&v,&w); //读入边的起点和终点
        if(u==-1 && v==-1 && w==-1) break;
       if(w<mapp[u][v])  //这样就可以保证图中存的是两点间的最短距离.
           Edge[u][v]=w;   //构造邻接矩阵（这里的输入也说明了它是单向的,既有向）//对应的无向图改下就行了.
    }
    dijkstra( 0 );//求顶点0到其他路径的最短路径.//求单源路劲最短.
    int shortest[maxn];//输出最短路径上的各个顶点时存放各个顶点的序号.
    for(i=1;i<n;i++){
        printf("%d\t",dist[i]);//输出顶点0到顶点i的最短路径长度.
        memset(shortest ,0,sizeof(shortest));//path数组的作用在这里,因为后面要输出,所以必须要一个数组来保存路径.
        int k=0;
        shortest[k]=i;
        /*for(int i=0;i<n;i++){
            printf("%d ",path[i]);
        }
        putchar('\n');*/
        while(path[shortest[k]]!=0)//这里的作用就是回溯输出路径.不懂就写出来看下就可以了.
        {
            k++;
            shortest[k]=path[shortest[k-1]];
        }
        k++;
        shortest[k]=0;
        for(j=k;j>0;j--)
            printf("%d-->",shortest[j]);
        printf("%d\n",shortest[0]);
    }
}

第二种 最暴力 的算法,floyd(适用于点数比较少的情况，允许有权值为负的边)(可以打印任意两点间的最短距离)(复杂度飞常高,不是一定要用,则尽量不要用)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e4+5;
const int inf=1e9+7;
int edge[maxn][maxn];//点i到j的距离.
int n;
void floyd()//可以找到任意两点的最短距离.
{
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]);
                //暴力每一点到每一点所有的可能性,三重循环的纯暴力方法.
                //如果不是很明白,则写出来看看就可以了.
                //循环顺序不能变,否则会WA,现在不是太懂,等懂了再来解释,现在先记住顺序必须是这样的!
//因为必须要固定中间那个点, 去枚举起点和终点, 这样对于每一条边都会去松弛, .
//而交换了顺序后是中间那个点在不断变换, 所以对于有些边更新时还是初始值之间进行更新,这样就是错的.
            }
        }
    }
}
/*核心思想为开始允许可以从第一个点中转,然后允许才能够1,2中转,到最后1~n中转,找到每两个点之间的最短路.*/

int main()
{
    int i,j;//循环变量.
    int u,v,w;//边的起点与终点及权值.
    scanf("%d",&n);//顶点个数
    for(i=0;i<n;i++){
       for(j=0;j<n;j++){
            if(i==j)  edge[i][j]=0;
            else  edge[i][j]=INF;
        }
    }
    while(1)
    {
        scanf("%d %d %d",&u,&v,&w); //读入边的起点和终点
        if(u==-1 && v==-1 && w==-1) break;
        if(w<mapp[u][v])  //这样就可以保证图中存的是两点间的最短距离.
            edge[u][v]=w;   //构造邻接矩阵（这里的输入也说明了它是单向的,既有向）//对应的无向图改下就行了.
    }
    /*for(i=0;i<n;i++)//打印邻接矩阵.
    {
        for(j=0;j<n;j++)
        {
            printf("%d ",edge[i][j]);
        }
        printf("\n");
    }*/
    floyd();
    for(int i=0;i<=5;i++){
        printf("%d ",edge[1][i]);//打印1到其余点的最短路径.//可以打印任何点到任一点的距离.
    }
    printf("\n");
}

第三种,SPFA算法,这个算法是最好的,也可以适用于权值有负的边,时间复杂度也是最低的.(也是可以优化的+SLF,可以去网上搜搜模板)(求源点到其余点的最短距离)

(这个是单纯求最短路的,下面还有用这个算法去求该图有无负环的)
(判断负环就是对每一个入队点数进行标记,当入队次数超过了一定的范围是,可以判断该图中存在负环可以上网搜搜(一般图中为2次,具体怎么证明的也不是很清楚))
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=1e6;
const int maxp=1e4+5;
const int eps=1e-6;
const int inf=1e9;      //这个inf必须足够大,否则会影响后面的判断的.(int 不够 就用 ll  )
int cas=1;
int edge[maxp][maxp];
int vis[maxp],dis[maxp];
queue<int>q;
int n,m;
void spfa(int u)
{
    CLR(vis);
    vis[u]=1;
    q.push(u);
    dis[u]=0;
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        vis[tmp]=0;//消除标记.
        for(int i=1;i<=n;i++){
            if(dis[i] > edge[tmp][i]+dis[tmp]){
                dis[i]=edge[tmp][i]+dis[tmp];
                if(!vis[i]){
                    vis[i]=1;//进行入队标记.
                    q.push(i);
                }
            }
        }
    }
}
int main()//水题是hdu2544(三种方法都适用)
{
    while(~scanf("%d %d",&n,&m)){
        if(n==0 && m==0)
            break;
       for(int i=1;i<=n;i++){
            dis[i]=inf;
            for(int j=1;j<=n;j++){
                if(i==j)   edge[i][j]=0;
                else  edge[i][j]=inf;
            }
        }
        for(int i=0;i<m;i++){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
             if(w<edge[u][v])  //这样就可以保证图中存的是两点间的最短距离.
                 edge[u][v]=edge[v][u]=w;
        }
        /*for(int i=1;i<=n;i++){//打印临接表出来看下.
            for(int j=1;j<=n;j++){
                printf("%d ",edge[i][j]);
            }
            printf("\n");
        }*/
        while(!q.empty())
        {
            q.pop();
        }
        spfa(1);//从1到其他任何点的最短距离.
        printf("%d\n",dis[n]);
    }
}

所以题目要是要求求任意两点间的最短距离,则用floyd算法

spfa算法的栈写法(其实跟队列是基本一样的,就是把队列的地方改成栈就可以了,就是可能内存或运行效率有点不同,看下知道有这种写法就可以了)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stack>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=1e6;
const int maxp=1e4+5;
const int eps=1e-6;
const int inf=1e9;    //这个inf必须足够大,否则会影响后面的判断的.(int 不够 就用 ll  )
int cas=1;
int edge[maxp][maxp];
int vis[maxp],dis[maxp];
stack<int>s;
int n,m;
void spfa_dfs(int u)
{
    CLR(vis);
    vis[u]=1;
    s.push(u);
    dis[u]=0;
    while(!s.empty())
    {
        int tmp=s.top();
        s.pop();
        vis[tmp]=0;
        for(int i=1;i<=n;i++){
            if(dis[i] > edge[tmp][i]+dis[tmp]){
                dis[i]=edge[tmp][i]+dis[tmp];
                if(!vis[i]){
                    vis[i]=1;
                    s.push(i);
                }
            }
        }
    }
}
int main()//水题是hdu2544(三种方法都适用)
{
    while(~scanf("%d %d",&n,&m)){
        if(n==0 && m==0)
            break;
       for(int i=1;i<=n;i++){
            dis[i]=inf;
            for(int j=1;j<=n;j++){
                if(i==j)   edge[i][j]=0;
                else  edge[i][j]=inf;
            }
        }
        for(int i=0;i<m;i++){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            if(w<edge[u][v])  //这样就可以保证图中存的是两点间的最短距离.
                edge[u][v]=edge[v][u]=w;
        }
        /*for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                printf("%d ",edge[i][j]);
            }
            printf("\n");
        }*/
        while(!s.empty())
            s.pop();
        spfa_dfs(1);//从1到其他任何点的最短距离.
        printf("%d\n",dis[n]);
    }
}
//对比也能发现根本就没什么两样.

附上有临接链表写的spfa,因位大部分都是用的这种方法写的,据说是更快,更省内存.(如果要写spfa算法的话,就用这种方法写,就不要用上面两种方法了，避免超时!)
这是水题 poj --- 3013 题目在此的spfa写法.
(对于最短路中,dij要T的就一般用spfa了,即对于点和路比较多的那种用spfa,点比较少的用普通的dij和floyd就行.)

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
using namespace std;
const int maxn=1e6+5;
const ll inf=1e15;      //这个inf必须足够大才行,否则会一直WA.!!!这是坑点,坑了我好久.
int head[maxn];
int weight[maxn];
ll dis[maxn],vis[maxn];
int n,m,ans;
struct node
{
    int to;
    int v;
    int next;
}edge[maxn];    //边跟点的范围要分清楚,不要开成一样的了,否则会WA!!!

void add(int a,int b,int v)
{
    edge[ans].to=b;   //a可以到b点.
    edge[ans].v=v;    //v是两点间的距离.
    edge[ans].next=head[a];    //结束标记,表示没有再于a点相连的点了.
    head[a]=ans++;
}

void spfa(int u)
{
    queue<int >q;
    dis[u]=0;
    vis[u]=1;
    q.push(u);
    while(!q.empty()){
        int k=q.front();   //从不断入队中的元素中不断进行循环的那个步骤,直到队列为空.
        //printf("%d\n",k);
        q.pop();
        vis[k]=0;
        for(int i=head[k];i!=-1;i=edge[i].next)//懂不起写出来就可以了.
        {          //headx表示提取与x直接相连的点的信息.然后直到提取到head为-1时(初始化值),表示提取完毕,即结束.(然后进行下一个开头的提取.)
            int m=edge[i].to;
            if(dis[m]>dis[k]+edge[i].v){//意思是u点到m点的距离如果大于u点到k点再到m点的距离的话.
                dis[m]=dis[k]+edge[i].v;
                if(!vis[m]){
                    vis[m]=1;
                    q.push(m);
                }
            }
        }
    }
}

void solve()
{
    CLR(vis);
    memset(head,-1,sizeof(head));
    ans=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        scanf("%d",&weight[i]);
    }
    for(int i=0;i<m;i++){    //因为这个
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);（保证两个点之间不会有多条路）.
        add(u,v,w);//因为是无向图,所以要加两次.
        add(v,u,w);
    }
    spfa(1);
    ll ans=0;
    int flag=1;
    for(int i=2;i<=n;i++){
        if(dis[i]==inf){
            flag=0;
            break;
        }
        ans+=weight[i]*dis[i];//为什么这样算也可以得出正确答案,是推出来的.请看下面
        printf("%I64d\n",ans);
    }
    if(flag)
        printf("%I64d\n",ans);
    else
        printf("No Answer\n");//不能将所有点都连接起来.

}
int main()  //用的临接链表做的.速度快,内存小.(用的数组模拟的)
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
}
/*
第二个样例中的计算方法
4*40+3*50+2*60+3*(20+40+50+60)+2*30+1*(10+20+30+40+50+60)
=10*1+20*(1+3)+30*(2+1)+40*(4+1+3)+50*(3+1+3)+60*(1+2+3)
=10+80+90+320+350+360
=1210
所以得出来的公式.(ans+=weight[i]*dis[i]).
*/