// Dijkstra.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
 
#include "stdafx.h"
#include <iostream>
#include <stack>
#define MAX_VALUE 1000
using namespace std;
 
struct MGraph
{
 int *edges[MAX_VALUE];
 int iVertexCount, iEdageCount;
};
void ReadDate(MGraph *mGraph, int *iBegin, int *iEnd);
void Dijkstra(MGraph *mGraph, int *pArrDis, int *pArrPath, int iBegin);
void PrintResult(int *pArrDis, int *pArrPath, int iBegin, int iEnd);
 
int main()
{
 int iBegin, iEnd;
 int *pArrPath = new int[MAX_VALUE];
 int *pArrDis = new int[MAX_VALUE];
 MGraph mGraph;
 for (int i = 0; i < MAX_VALUE; i++){
 mGraph.edges[i] = new int[MAX_VALUE];
 }
 ReadDate(&mGraph, &iBegin, &iEnd);
 Dijkstra(&mGraph, pArrDis, pArrPath, iBegin);
 PrintResult(pArrDis,pArrPath, iBegin, iEnd);
 system("pause");
 return 0;
}
 
void ReadDate(MGraph *mGraph, int *iBegin, int *iEnd){
 cout << "請(qǐng)輸入頂點(diǎn)數(shù)量" << endl;
 cin >> mGraph->iVertexCount;
 cout << "請(qǐng)輸入鄰接矩陣數(shù)據(jù)：" << endl;
 for (int iRow = 1; iRow <= mGraph->iVertexCount; iRow++){
 for (int iCol = 1; iCol <= mGraph->iVertexCount; iCol++){
  cin >> mGraph->edges[iRow][iCol];
 }
 }
 
 //cout << "請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)" << endl;
 //cin >> mGraph->iVertexCount >> mGraph->iEdageCount;
 //for (int iRow = 1; iRow <= mGraph->iVertexCount; iRow++){
 // for (int iCol = 1; iCol <= mGraph->iVertexCount; iCol++){
 // mGraph->edges[iRow][iCol] = -1;
 // }
 //}
 //cout << "請(qǐng)輸入連通邊及權(quán)重" << endl;
 //int iRow, iCol, iWeight;
 //for (int i = 1; i <= mGraph->iEdageCount; i++){
 // cin >> iRow >> iCol >> iWeight;
 // mGraph->edges[iRow][iCol] = iWeight;
 //}
 
 cout << "請(qǐng)輸入查詢(xún)的起點(diǎn)和終點(diǎn)" << endl;
 cin >> *iBegin >> *iEnd;
}
 
void Dijkstra(MGraph *mGraph, int *pArrDis, int *pArrPath, int iBegin){
 int iMin;
 int bArrVisited[MAX_VALUE];
 memset(bArrVisited, false, sizeof(bArrVisited));
 for (int i = 1; i <= mGraph->iVertexCount; i++){
 pArrPath[i] = -1;
 mGraph->edges[i][i] = 0;
 pArrDis[i] = mGraph->edges[iBegin][i] != -1 ? mGraph->edges[iBegin][i] : INT_MAX;
 }
 int iNewCost;
 int iSelected = iBegin;
 
 for (int i = 1; i <= mGraph->iVertexCount; i++){
 int iPre = iSelected;
 iMin = INT_MAX;
 for (int j = 1; j <= mGraph->iVertexCount; j++){
  if (!bArrVisited[j] && pArrDis[j] < iMin){
  iMin = pArrDis[j];
  iSelected = j;
  }
 }
 for (int j = 1; j <= mGraph->iVertexCount; j++){
  iNewCost = pArrDis[iSelected] != -1 && mGraph->edges[iSelected][j] != -1 ? pArrDis[iSelected] + mGraph->edges[iSelected][j] : INT_MAX;
  if (!bArrVisited[j] && iNewCost < pArrDis[j]){
  pArrPath[j] = iSelected;
  pArrDis[j] = iNewCost;
  //pArrPath[iSelected] = iSelected;
  }
 }
 //pArrPath[iSelected] = iPre;
 bArrVisited[iSelected] = true;
 }
}
 
void PrintResult(int *pArrDis, int *pArrPath, int iBegin, int iEnd){
 
 cout << "從" << iBegin << "開(kāi)始到" << iEnd << "的最短路徑長(zhǎng)度為";
 cout << pArrDis[iEnd] << endl;
 cout << "所經(jīng)過(guò)的最短路徑節(jié)點(diǎn)為：";
 
 stack<int> stackVertices;
 int k = iEnd;
 do{
 k = pArrPath[k];
 stackVertices.push(k);
 } while (k != pArrPath[k] && k != -1);
 cout << stackVertices.top()*-1;
 stackVertices.pop();
 
 unsigned int nLength = stackVertices.size();
 for (unsigned int nIndex = 0; nIndex < nLength; nIndex++)
 {
 cout << " -> " << stackVertices.top();
 stackVertices.pop();
 }
 cout << " -> " << iEnd << endl;
}