#include "Dijkstra.h"
#include <string>
using namespace std;
/*
* （1）二维数组存储输入的边的权重数据，数组的下标表示指向。
* （2）存储输出结果的对象指针。
* （3）输入数据的顶点数和边上权重的两个变量。
*/
Dijkstra::Dijkstra(int Num1, int Num2)
{
vertexNum = Num1;
sideNum = Num2;
/* 变量内存的申请 */
//二维指针数组的堆上内存的申请
sideDataMatrix = new int*[vertexNum];
for (int i = 0; i < vertexNum; i++)
{
sideDataMatrix[i] = new int[vertexNum];
}
for (int i = 0; i < vertexNum; i++)
{
for (int j = 0; j < vertexNum; j++)
{
sideDataMatrix[i][j] = INT_MAX;
}
}
dijkstraDataArray = new DijkstraData[vertexNum];
}
Dijkstra::Dijkstra()
{
}
Dijkstra::~Dijkstra()
{
/* 申请内存变量控件的清理 */
for (int i = 0; i < vertexNum; i++)
{
delete[] sideDataMatrix[i];
}
delete[] dijkstraDataArray;
}
/*
* （1）输入顶点数和边权重的存储函数
* （2）边权重数的存储函数
* （3）权重存储的数组的打印
* （4）Dijkstra算法的实现
* （5）最短路径的打印函数
*/
void Dijkstra::setDijkstraData(int Num1, int Num2)
{
vertexNum = Num1;
sideNum = Num2;
/* 变量内存的申请 */
//二维指针数组的堆上内存的申请
sideDataMatrix = new int* [vertexNum];
for (int i = 0; i < vertexNum; i++)
{
sideDataMatrix[i] = new int[vertexNum];
}
for (int i = 0; i < vertexNum; i++)
{
for (int j = 0; j < vertexNum; j++)
{
sideDataMatrix[i][j] = INT_MAX;
}
}
dijkstraDataArray = new DijkstraData[vertexNum];
}
void Dijkstra::saveSideByVertex(int start, int end, int sidedata)
{
if ((start > 0) && (start <= sideNum) && (end > 0) && (end <= sideNum) && (sidedata > 0))
{
sideDataMatrix[start-1][end-1] = sidedata;
//cout << start << "," << end << "," << sidedata <<"," << sideDataMatrix[start][end] << endl;
}
else
{
cout << "输入数据错误" << endl;
}
}
void Dijkstra::printSideDataMatrix()
{
cout << "节点数据的结构体：" << endl;
for (int i = 0; i < vertexNum; i++)
{
for (int j = 0; j < vertexNum; j++)
{
if (sideDataMatrix[i][j] == INT_MAX)
cout << "∞";
else
cout << sideDataMatrix[i][j];
cout << " ";
}
cout << endl;
}
cout << endl;
}
/* Dijkstra算法的主要函数,begin设置起始点 */
void Dijkstra::DijkstraFunction(int begin)
{
int count = 0;
/* 设置字符串中的路径,以及初始点的周围指向权重 */
for (int i = 0; i < vertexNum; i++)
{
dijkstraDataArray[i].path = "v" + to_string(begin) + "-->v" + to_string(i+1);
dijkstraDataArray[i].sideDataMin = sideDataMatrix[begin-1][i];
}
/* 设置起点路径，设置指向自己的权重为0 */
dijkstraDataArray[begin - 1].isMin = true;
dijkstraDataArray[begin - 1].sideDataMin = 0;
/* 最短路径的计算 */
while (count != vertexNum)
{
int temp = 0;
int min = INT_MAX;
/* 找出来dijkstraDataArray数组中的总权重最小值 */
for (int i = 0; i < vertexNum; i++)
{
if ((!dijkstraDataArray[i].isMin) && (dijkstraDataArray[i].sideDataMin < min))
{
min = dijkstraDataArray[i].sideDataMin;
temp = i;
}
}
dijkstraDataArray[temp].isMin = true;
count++;
/* 分析临近节点权重最小的线路，更新到对应的权重 */
for (int i = 0; i < vertexNum; i++)
{
if ((sideDataMatrix[temp][i] != INT_MAX) && \
(!dijkstraDataArray[i].isMin) && \
((sideDataMatrix[temp][i] + dijkstraDataArray[temp].sideDataMin) < dijkstraDataArray[i].sideDataMin))
{
cout << dijkstraDataArray[i].sideDataMin << endl;
dijkstraDataArray[i].sideDataMin = dijkstraDataArray[temp].sideDataMin + sideDataMatrix[temp][i];
dijkstraDataArray[i].path = dijkstraDataArray[temp].path+ "-->v" + to_string(i+1);
}
}
}
}
void Dijkstra::printMinPath()
{
cout << "搜索到的V1到Vi的最短路径" << endl;
for (int i = 0; i < vertexNum; i++)
{
if (dijkstraDataArray[i].isMin && (dijkstraDataArray[i].sideDataMin != INT_MAX))
{
cout << dijkstraDataArray[i].path << "=" << dijkstraDataArray[i].sideDataMin << endl;
}
else
{
cout << dijkstraDataArray[i].path << " " << "没有路径" << endl;
}
}
}
