Dijkstra算法算最短路径

Dijkstra算法算最短路径
急求一个Dijkstra算最短路径的代码,要完整的（包括头文件,生成距阵）,可直接运行的.

////////////////////////////////////////////////////////////
// Graph.h
#pragma once
#define maxPoint 100
class CGraph
{
public:
CGraph(void);
CGraph(void);
bool SetGraph( double g[maxPoint][maxPoint] ,int startPoint ,int size );
bool Dijkstra();
void Display();
int GetStartPoint();
double GetBestWay( int dest ,int path[] ,int &pathLen );
private:
//标志当前图是否已经求解
bool solved;
//当前图布局
double graph[maxPoint][maxPoint];
//地图大小
int size;
//起点
int startPoint;
//当前图的解
double dist[maxPoint];
int prev[maxPoint];
};
////////////////////////////////////////////////////////////
// Graph.cpp
#include 'StdAfx.h'
#include '.\graph.h'
CGraph::CGraph(void)
{
for( int i = 0 ; i < maxPoint ; i++ )
{
for( int j = 0 ; j < maxPoint ; j++ )
graph[i][j] = -1;
}
startPoint = -1;
size = -1;
//当前图还没有求解
solved = false;
}
CGraph::CGraph(void)
{
}
//
//
bool CGraph::SetGraph( double g[maxPoint][maxPoint] ,int startPoint ,int size )
{
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
graph[i][j] = g[i][j];
}
this->startPoint = startPoint;
this->size = size;
solved = false;
Dijkstra();
return true;
}
//
//
bool CGraph::Dijkstra()
{
bool s[maxPoint];
for( int j = 0 ; j < size ; j++ )
{
dist[j] = graph[startPoint][j];
s[j] = false;
//dist[i] 0 && dist[j] < temp )
{
u = j;
temp = dist[j];
}
}
else
{
u = j;
temp = dist[j];
flag = true;
}
}
}
s[u] = true;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] && graph[u][j] > 0 )
{
double newDist = dist[u] + graph[u][j];
if( dist[j] < 0 || newDist < dist[j] )
{
dist[j] = newDist;
prev[j] = u;
}
}
}
}
//标记当前问题已经解决
solved = true;
return true;
}
//
//
void CGraph::Display()
{
printf( '当前地图的邻接矩阵\n' );
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
{
printf( '%5.f' ,graph[i][j] );
}
printf( '\n' );
}
}
//
//
double CGraph::GetBestWay( int dest ,int path[] ,int &pathLen )
{
int p = dest;
int theway[maxPoint];
int len = 0;
while( p != startPoint )
{
theway[len] = p;
p = prev[p];
len++;
}
theway[len] = startPoint;
len++;
for( int i = 0 ,j = len - 1 ; i < len ; i++ ,j-- )
path[i] = theway[j];
pathLen = len;
return dist[dest];
}
//
//
int CGraph::GetStartPoint()
{
return startPoint;
}
//
////////////////////////////////////////////////////////////
// Dijkstra.cpp :定义控制台应用程序的入口点.
//
#include 'stdafx.h'
#include 'conio.h'
#include 'Graph.h'
int _tmain(int argc,_TCHAR* argv[])
{
double graph[][maxPoint] =
{
{ 1 ,10 ,-1 ,30 ,100 } ,
{ -1 ,0 ,50 ,-1 ,-1 } ,
{ -1 ,-1 ,0 ,-1 ,10 } ,
{ -1 ,-1 ,20 ,0 ,60 } ,
{ -1 ,-1 ,-1 ,-1 ,-1 }
};
int size = 5;
int start = 0;
int dest = 1;
int pathlen;
int path[maxPoint];
double dist;
CGraph g;
g.SetGraph( graph ,start ,size );
g.Display();
printf( '----------------------------------------\n' );
for( dest = 0 ; dest < size ; dest++ )
{
dist = g.GetBestWay( dest ,path ,pathlen );
printf( '从 %d 到 %d 的最短路径长 %.f\n' ,g.GetStartPoint() ,dest ,dist );
printf( '所经结点为:\n' );
for( int i = 0 ; i < pathlen ; i++ )
printf( '%3d' ,path[i] );
printf( '\n----------------------------------------\n' );
}
getch();
return 0;
}
////////////////////////////////////////////////////////////
// 程序说明：
// 本程序在 VC++.NET 2003 上调试通过
// 首先建立 Win32控制台应用程序,工程名为 Dijkstra
// 工程设置默认
// 添加 一般C++类 CGraph
// 填写以上内容