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

Mei笑D小妞

　　题目大致就是找到一个图的最短路径，没什么新意，不过关键是！关键是！我没写出来……
　　上上篇文章——图的所有路径输出可以解决，不过要计算所有路径，工作量比较大，可能是超时。
　　对于这种无负边的最短路径可以用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 != startPoint)
     {
         v.push_back(path);
         s = path;
     }
     v.push_back(startPoint);

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

void PrintIntVector(vector<int> v)
{
     for (int i = 0; i < v.size(); i++)
     {
         cout << v << "\t";
     }
     cout << endl;
}
void PrintBoolVector(vector<bool> v)
{
     for (int i = 0; i < v.size(); i++)
     {
         cout << v << "\t";
     }
     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 = false;
         D = map[startPoint];
         //有边
         if (D >0)
         {
             Path = startPoint;
         }
         else
         {
             Path = -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 == false && D != -1 && (D < min))
             {
                 v = i;
                 min = D;
             }
         }
         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 == false && map[v] != -1 && (D[v] + map[v] < D || D == -1))
             {
                 D = D[v] + map[v];
                 Path = 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;
}
View Code　　结果如下