Dijkstra最短路径——2017华为实习在线机试

题目大致就是找到一个图的最短路径，没什么新意，不过关键是！关键是！我没写出来……

上上篇文章——图的所有路径输出可以解决，不过要计算所有路径，工作量比较大，可能是超时。

对于这种无负边的最短路径可以用Dijkstra求解。

代码注释很全，可以直接看懂：

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
#include <stack>
#include <queue>

using namespace std;

typedef struct point{
    int x;
    int y;
    point *previous;
    int step;
} point;

/*
int map[6][6] = {
    { 0, 2, 10, 5, 3, -1 },
    { -1, 0, 12, -1, -1, 10 },
    { -1, -1, 0, -1, 7, -1 },
    { 2, -1, -1, 0, 2, -1 },
    { 4, -1, -1, 1, 0, -1 },
    { 3, -1, 1, -1, 2, 0 }
};*/
int map[6][6] = {
    { -1, 2, 10, -1, 3, -1 },
    { -1, -1, 12, -1, -1, 10 },
    { -1, -1, -1, -1, 7, -1 },
    { -1, -1, -1, -1, -1, -1 },
    { 4, -1, -1, -1, -1, -1 },
    { 3, -1, 1, -1, 2, -1 }
};
/*
int map[6][6] = {
    {-1,-1,10,-1,30,100},
    {-1,-1,5,-1,-1,-1},
    {-1,-1,-1,50,-1,-1},
    {-1,-1,-1,-1,-1,10},
    {-1,-1,-1,20,-1,60},
    {-1,-1,-1,-1,-1,-1},
};*/
/*
int map[6][6] = {
    { -1, -1, 10, -1, 30, 100 },
    { -1, -1, 5, -1, -1, -1 },
    { -1, -1, -1, 50, -1, -1 },
    { -1, -1, -1, -1, -1, 10 },
    { -1, -1, -1, 20, -1, 60 },
    { -1, -1, -1, -1, -1, -1 },
};*/

void PrintMostShortPath(vector<int> path, vector<int> D, int startPoint, int endPoint)
{
    int s = endPoint;
    vector<int> v;
    v.push_back(endPoint);

    while (path[s] != startPoint)
    {
        v.push_back(path[s]);
        s = path[s];
    }
    v.push_back(startPoint);

    cout << "最短路径为：";
    for (int i = v.size() - 1; i >= 0; i--)
    {
        cout << " " << v[i];
    }
    cout << endl;
    cout << "最距离为为：" << D[endPoint] << endl;
}

void PrintIntVector(vector<int> v)
{
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << "	";
    }
    cout << endl;
}
void PrintBoolVector(vector<bool> v)
{
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << "	";
    }
    cout << endl;
}

//算法对于负边图无效
void Dijkstra(int startPoint,int endPoint)
{
    //获取图边长
    int n = 6;

    //初始化变量
    vector<bool> S(n);//标记节点是否走过
    vector<int> D(n);//从起点到该点的最短距离
    vector<int> Path(n);//该点的前驱节点
    int v = 0;
    int min = 0;

    //初始化变量
    for (int i = 0; i < n; i++)
    {
        S[i] = false;
        D[i] = map[startPoint][i];
        //有边
        if (D[i] >0)
        {
            Path[i] = startPoint;
        }
        else
        {
            Path[i] = -1;
        }
    }
    S[startPoint] = true;
    D[startPoint] = 0;

    //初始化打印
    cout << "已经走过的节点S:    "; PrintBoolVector(S);
    cout << "当前最短路径D:        "; PrintIntVector(D);
    cout << "前驱符号Path：        "; PrintIntVector(Path);

    //再循环n-1次，把剩下的n-1个节点都走一遍
    for (int j = 1; j < n; j++)
    {
        min = 32767;
        v = 0;

        //寻找当前最短路径D中，未走过并且，可以到达的，距离最短节点。
        for (int i = 0; i < n; i++)
        {
            if (S[i] == false && D[i] != -1 && (D[i] < min))
            {
                v = i;
                min = D[i];
            }
        }
        S[v] = true;//v为中转节点，标记走过

        //以v为中转点走到i节点和现有到i路径比较
        for (int i = 0; i < n; i++)
        {
            //这个||很关键。两种需要更新的情况。一种是通过中转小于目前的最短距离，另一种是直接可以到的（在map中有v到i的路径）
            //第一个：没走过的点，第二个：能走的点，第三个：1.通过中转点走比直接走小2.在map中v-i可以走，但是在D中未更新的情况
            //dijkstra关键有就是一个更新的操作
            if (S[i] == false && map[v][i] != -1 && (D[v] + map[v][i] < D[i] || D[i] == -1))
            {
                D[i] = D[v] + map[v][i];
                Path[i] = v;
            }
        }

        //打印每次的结果
        cout << "第" << j << "次：" << endl;
        cout << "已经走过的节点S:    "; PrintBoolVector(S);
        cout << "当前最短路径D:        "; PrintIntVector(D);
        cout << "前驱符号Path：        "; PrintIntVector(Path);
    }
    PrintMostShortPath(Path, D, startPoint, endPoint);
}

int main()
{
    int startPoint = 4;
    int endPoint = 1;

    Dijkstra(startPoint, endPoint);

    return 0;
}

结果如下