朴素的dijkstra最短路径算法

dijkstra算法适用于无负权图中求最短路径，时间复杂度为O(n^2+e),n为节点数，e为边数

需要的数据：

1.n行两列数组arr[n][2],第一列记录当前节点到出发点的最短距离，第二列记录当前节点前面路过的节点
2.n长度的bool型数组pd[n]，记录是否已经被选择过
3.vector类n行数组vis[n][]，记录该行对应的节点到此行某列对应的下标的节点的距离

操作流程：

0.初始化：将图保存到vis中，pd数组元素初始值为1，表示可选，arr第一列除起点外全部初始化为无穷大，第二列可不初始化。

1.设当前节点it=起点

2.pd[it]赋值为0，表示已经经过此点不再经过,遍历vis[it],设当前遍历的节点为i，设v为经过it节点到i节点的最短距离，v=arr[0][it]+vis[it][i],即从起点到it节点的最短距离加上从it节点到i节点的距离，如果v<arr[0][i]则更新arr[0][i]为v，并更新arr[1][i]为it,表示经过it节点到i节点的距离更短.

3.同时遍历pd和arr[0],找出pd[i]==1且arr[0][i]值最小的节点i,当前节点it赋值为i.

4.重复2，3，直到pd中元素全部为0时返回arr[0][终点]即为起点到终点的最短路径。

证明

详见算法导论

难点

将图转化为二维vector数组。

伪代码：

#define maxn 8
struct node
{
    int v;
    int last_node;
    node()
    {
        v=last_node=0;
    }
    node(int a,int b):v(a),last_node(b){};
};
int arr[maxn][2];
bool pd[maxn]={1};
vector<node>vis[maxn];
int dijkstra(int start,int end)
{
    for(int i=0;i<maxn;i++)
    {
        arr[0][i]=10000;
    }
    arr[0][start]=0;
    while(1)
    {
        int it=-1;
        int minv=10000;
        for(int i=0;i<maxn;i++)
        {
            if(minv<arr[0][i]&&pd[i])
            {
                minv=arr[0][i];
                it=i;
            }
        }
        pd[it]=0;
        if(it==-1)
        {
            return arr[0][end];
        }
        int len=vis[it].size();
        for(int i=0;i<len;i++)
        {
            int v=vis[it][i].v+arr[0][it];
            if(v<arr[0][i])
            {
                arr[0][i]=v;
                arr[1][i]=it;
            }
        }
    }
}