单源最短路径问题[Dijkstra实现](邻接矩阵)

单源最短路径问题[Dijkstra实现]

一、问题

 带权有向图G（E,V), 找出从给定源顶点s到其它顶点v的权最小路径。

“最短路径” = 最小权

其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

效率方面，因为每次都要从都要从Dn里找最小Dv，所以时间效率是V²的。如果是稠密图，基本上程序比较优了。关于稀疏图用优先队列，二叉堆优化神马的，以后再看...如果需要每个顶点作为源的所有最短路，在稠密图下，Floyd比循环n次Dijkstra稍快，且简洁。

二、问题求解：

求1到5的最短路径值？

三、执行过程：

 

如果大家对这个问题的要求还不是很明白的话那么我再带着大家走一遍：

第一次：从1-->2：10 此时从1-->3没有路径所有是无穷大  1-->4：30  1-->5：100那么我们发现这一组组最小的是10也就是2这一点，所以我们再把2这一点加到集合里面来，那么2这一点就可以当作一个桥来用，

第二次：此时我们再从1到3就可以通过1-->2-->3:60其他的1-->4：30 ，1-->5：100 可以发现此时最小的应该是4，所以我们再把4这一点加入到这个集合里面来，如此重复的去做这些事情，

到最后可以发现1到5的最短路径应该是60（1-->4-->3-->5）

一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。 

int dijkstra(int s,int t)
{

       初始化S={空集}

       d[s] = 0; 其余d值为正无穷大

       while (NOT t  in S)

       {

              取出不在S中的最小的d[i];

              for (所有不在S中且与i相邻的点j)

                if (d[j] > d[i] + cost[i][j])
                d[j] = d[i] + cost[i][j]; ( “松弛”操作” )

              S = S + {i}; //把i点添加到集合S里

       }

       return d[t];

}

#include <iostream>

using namespace std;

#define MAX 9999999

#define LEN 210

int map[LEN][LEN];    //某点到某点两点间的的距离
int dist[LEN];        //记录当前点到源点的最短路径长度
int mark[LEN];        //加入进来的点的集合



    //初始化map为正无穷大
    void init()
    {
       int i,j;
       for(i=0;i<LEN;i++)
       {
              for(j=0;j<LEN;j++)
              {
                     map[i][j]=MAX;
              }
       }
    }

    //n:多少条路  start:起始点
    //dist[i],最后存储着start 到i点的最短距离
    void myDijstra(int n,int start)
    {
       int i,j,min,pos;
       for(i=1;i<=n;i++)
       {
            mark[i]=0;//没有点加入
            dist[i]=map[start][i];//把start 附近点 dis[]初始化
       }

       mark[start]=1;//把起始点加进来
       dist[start]=0;

       for(i=1;i<=n;i++)
       {

              min=MAX;
              for(j=1;j<=n;j++)
              {
                     if(!mark[j] && dist[j]<min)
                     {    //取出不在mark里的最小的dist[i]
                         min=dist[j];
                         pos=j;//标记
                     }

              }

              if(min==MAX)//已经不能通了
                  break;

                mark[pos]=1;//把K加进来

              //做松弛操作
              for(j=1;j<=n;j++)
              {
                    if(!mark[j] && dist[j]>dist[pos]+map[pos][j])//start->j or start->pos,pos->j
                    {
                       dist[j]=dist[pos]+map[pos][j];//这步跟prim算法有点不同
                    }
              }
        }
    }



int main(){

       int i,n,line;

       int a,b,d;
       scanf("%d%d",&n,&line);//输入点和
       init();
       for(i=0;i<line;i++)
       {

           scanf("%d%d%d",&a,&b,&d); //输入各边的权值
            //
这个判断是防止重边的，因为也许会对同一条路给出两个值，这时就保存较小的值             if(map[a][b]>d)
            {
            map[a][b]=map[b][a]=d;
            }
       }

       myDijstra(n,1);//调用方法(点数，起始点)

       //输出1到5的最短路径

       cout<<dist[5]<<endl;

       return 0;

}

/*
5 7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
60
*/

参考

http://blog.csdn.net/kootain/article/details/6683646
http://blog.csdn.net/jiahui524/article/details/6636913