通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是"起点s到该顶点的路径"。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。

/*************************************************
*  函数名称：dijkstra(int src)
*  功能描述：求无权图的任意点到其它顶点的距离
*  参数列表：src是起点
*  返回结果：void 
*************************************************/
void Graph::dijkstra(int src)
{
    //初始化顶点信息
    for(int i = 0; i < vertex_num; ++i){
        nodeArr[i].known = false;
        nodeArr[i].dist = INFINITY;
        nodeArr[i].path = 0;
    }
    //重要的一步，开启算法的关键一步
    nodeArr[src].dist = 0;
 
    for(; ;){
        //找到unknown的dist最小的顶点 
        int v = 0;
        int max = INFINITY;
        for(int i = 0; i < vertex_num; ++i){
            if(!nodeArr[i].known && (max > nodeArr[i].dist)){
                max = nodeArr[i].dist;
                v = i;
            }
        }
 
        //没有找到满足条件的顶点,退出算法
        if(max == INFINITY)
            break;
 
        nodeArr[v].known = true;
        //更新与v相邻所有顶点w的dist,path
        for(list<Node>::iterator it = graph_list[v].begin(); it != graph_list[v].end(); ++it){
            if(!nodeArr[(*it).vertex].known){
                if(nodeArr[v].dist + (*it).weight < nodeArr[(*it).vertex].dist){
                    nodeArr[(*it).vertex].dist = nodeArr[v].dist + (*it).weight;
                    nodeArr[(*it).vertex].path = v;
                }
            }
        }
 
    }
}

/*******************************************************
*  类名称： 邻接表图
********************************************************/ 
class Graph{
    private:
        int edge_num;//图边的个数
        int vertex_num;//图的顶点数目
        list<Node> * graph_list;//邻接表
        vector<GraphNode> nodeArr;//保存每个顶点信息的数组
        
    public:
        Graph(){}
        Graph(char* graph[], int edgenum); 
        ~Graph();
        void print();
        void dijkstra(int src);
        void printShorestPath(); 
    private:
        vector<int> get_graph_value(char* graph[], int columns);
        void addEdge(char* graph[], int columns);
};

int main(int argc, char *argv[])
{
    char *topo[5000];
    int edge_num;
    char *demand;
    int demand_num;
 
    char *topo_file = argv[1];
    edge_num = read_file(topo, 5000, topo_file);
    if (edge_num == 0)
    {
        printf("Please input valid topo file.\n");
        return -1;
    }
 
    int src;
    cout << "输入求最短路径的起点：";
    cin >> src;
 
    Graph G(topo, edge_num);
    G.print();
    
    cout << "Dijkstra: " << endl;
    G.dijkstra(src);
    G.printShorestPath();
 
 
    release_buff(topo, edge_num);
 
	return 0;
}