dijkstra 贪心法.txt

Dijkstra 贪心法求单源最短路径.Dijkstra算法是解单源最短路径问题的一个贪心算法。

Dijkstra 贪心法求单源最短路径2007-12-14 00:13
问题描述

给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。
另外，还给定 V 中的一个项点，称为源。
现在我们要计算从源到所有其他各项点的最短路径长度。
这里的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。



算法基本思想

Dijkstra算法是解单源最短路径问题的一个贪心算法。
其基本思想是，设置一个基点集合 S ，并不断地作贪心
选择来扩充这个集合。
一个项点属于集合 S 当且仅当从源到该项点的最短路
径长度已知。
初始时，S中仅含有源。设 u 是 G 的某一个项点，
我们把从源到 u 且中间只有经过 S 中项点的路称为
从源到 u 的特殊路径，并且数组 dist 来记录当前每个
项点所对应的最短特殊路径长度。
Dijkstra算法每次从 V-S 中取出具有最短特殊路径长度
的项点 u ，将 u 添加到 S 中，同时对数组 dist 作必要
的修改。


源程序:


////////////////////////////////////////////////////////////
// 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，表示没有路径连接 结点startPoint 与 结点j
   if( dist[j] < 0 )
    prev[j] = 0;
   else
    prev[j] = startPoint;
}
//从起点出发
dist[startPoint] = 0;
s[startPoint] = true;
for( int i = 0 ; i < size ; i++ )
{
   double temp;
   int u = startPoint;
   bool flag = false;
   for( int j = 0 ; j < size ; j++ )
   {
    if( !s[j] )
    {
     //如果不是第一次比较，temp u，都已经赋值，则
     if( flag )
     {
      if( dist[j] > 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 main(int argc, char * 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;
}

////////////////////////////////////////////////////////////