图：Dijkstra

Dijkstra：最短路径问题

使用广度优先方法解决最短路径问题

伪代码描述

  1 function Dijkstra(G, w, s)
  2 for each vertex v in V[G] //初始化 3 d[v] := infinity //将各点的已知最短距离先设成无穷大 4 previous[v] := undefined //各点的已知最短路径上的前趋都未知 5 d[s] := 0 //因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
  6 S := empty set
  7 Q := set of all vertices
  8 while Q is not an empty set // Dijkstra演算法主体 9 u := Extract_Min(Q)
 10 S.append(u)
 11 for each edge outgoing from u as (u,v)
 12 if d[v] > d[u] + w(u,v) //拓展边（u,v）。  w(u,v)为从u到v的路径长度。
 13 d[v] := d[u] + w(u,v) //更新路径长度到更小的那个和值。
 14 previous[v] := u //纪录前趋顶点 

代码书写过程：

1. 进行基本的结构体定义，图的建立（邻接矩阵/邻接表）
2. 初始化 Init_Graph 将Graph[][] = max

void InitGraph(int N)
{
    for(int i = 0;i <= N;i++)
        for(int j = 0;j <= N;j++)
    {
        Graph[i][j].cost = 999;
        Graph[i][j].len = 999;
    }
}

3. 初始化节点 Init_Visit，此步比较重要，每个节点的标记为未访问，每个节点的值或路径长度都更新为相应的图(邻接矩阵)的值，然后将出发的节点(所选中的节点)标记为已经访问，路径长度和花费依次置为0

void InitVisit(int N,int S)
{
    for(int i = 0;i <= N;i++)
    {   
        Visit[i].visit = 0;
        Visit[i].len = Graph[S][i].len;
        Visit[i].cost = Graph[S][i].cost;
    }
    Visit[S].cost = 0;
    Visit[S].len = 0;
    Visit[S].visit = 1;
}

4. Dijkstra算法，要求N -> S的最短路径

• 首先，我们需要按顺序找到第一个没有被访问过的点，因为我们要找路径的最短长度，所以定义一个Minpoint，用来记录找到的路径最小的点。---------因为考虑到第一次寻找，必须让Visit[Minpoint]的值大于所给的Visit[i]，因此我们所初始化的图大小全部为理论最大值，与上文的初始化相对应。

    for(int j = 1;j < N;j++)
    {
        int MinPoint = N;
        for(int i = 0;i < N;i++)
        {
            if(!Visit[i].visit&&Visit[i].len<Visit[MinPoint].len)
                MinPoint = i;
        }
        ......
    }

• 将Minpoint标记为已访问
• DKS关键步骤：对每个未访问的节点，取路径长度/路径花费最小的那一条路

Visit[MinPoint].visit = 1;
        for(int i = 0;i < N;i++)
        {
            if(!Visit[i].visit)
            {
                if(Visit[i].len > Visit[MinPoint].len + Graph[i][MinPoint].len)
                {
                    Visit[i].len = Visit[MinPoint].len + Graph[i][MinPoint].len;
                    Visit[i].cost = Visit[MinPoint].cost + Graph[i][MinPoint].cost;
                }
                if(Visit[i].len == Visit[MinPoint].len + Graph[i][MinPoint].len)
                {
                    if(Visit[i].cost > Visit[MinPoint].cost + Graph[MinPoint][i].cost)
                    {
                        Visit[i].cost = Visit[MinPoint].cost + Graph[MinPoint][i].cost;
                    }
                }
            }
        }
    }
}

• 使用for循环遍历，如果找到的Visit[i] i节点的值大于当前节点与对应路径（Graph[i][Point]）之和，更新Visit[i].len = Visit[MinPoint].len + Graph[i][MinPoint].len;
• 对于花费也是如此

Visit[i].cost = Visit[MinPoint].cost + Graph[i][MinPoint].cost;

• 对于路径相等的，取花费最少的(具体问题具体分析)

• 主函数

• 基本输入，进行邻接矩阵的定义，顺序需要注意

• 首先初始化图 Init_Graph 各元素全部赋值为最大

• 然后进行邻接矩阵的建立 Graph[i][j] = Graph[j][i] = 输入

• 初始化Visit（节点）

• 调用Dijkstra进行计算，输出