Dijkstra算法（邻接表实现）

Dijkstra算法是求最短路径的经典算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 

Dijkstra算法采用的是贪心算法的策略，也正是因为Dijkstra这种贪心的策略，导致了其在处理负权路上的无解，因此，使用Dijkstra算法的一大前提便是：

所处理的图中不能有负权边；

算法的基本思想是：每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

其基本步骤如下：

1、将所有顶点分为两部分：已知最短路程的顶点集合P和未知最短路程的顶点集合Q。用vis[i]表示，如果vis[i]=1则表示这个顶点在集合P中，反之顶点在集合Q中。
2、设置源点s到自己的最短路径为0。其余按照实际情况进行设置。
3、在集合Q的所有定点中选择一个离源点s最近的顶点加入到集合P。并考察所有以点u为起点的边，对每一条边进行松弛操作。
4、重复第三步，如果集合Q为空，算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

void Graph::Dijkstra(string begin)
{
    if(pointnum==0)
    {
        printf("don't have the graph\n");
        return;
    }
    memset(dis,inf, sizeof(dis));
    initvis();
    int index = mmp[begin],u;
    ArcNode* p = point[index].firstarc;
    while(p)
    {
        dis[mmp[p->name]]=p->wigth;
        p=p->next;
    }
    vis[index]=1;
    dis[index]=0;
    for(int i=0;i<pointnum-1;i++)
    {
        int minn=inf;
        for(int j=0;j<pointnum;j++)
        {
            if(!vis[j]&&dis[j]<minn)
            {
                minn=dis[j];
                u=j;
            }
        }
        //printf("u=%d\n",u);
        vis[u]=1;
        p=point[u].firstarc;
        while(p)
        {
            if(dis[mmp[p->name]]>dis[u]+p->wigth)
                dis[mmp[p->name]]=dis[u]+p->wigth;
            p=p->next;
        }
    }
    cout<<"Dijkstra:"<<endl;
    for(int i=0;i<pointnum;i++)
    {
        cout<<"from "<<begin<<" to "<<point[i].name<<" the shortest road is:";
        printf("  %d\n",dis[i]);
    }
}