问题描述

给定一个带权有向图 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 _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;
}

求的是arc数组中存储的第一个顶点到其他顶点的最短路径，结果存在dis数组中。

＃i nclude <stdio.h>
＃i nclude <malloc.h>

#define MAX 100
#define MAXNUM 10000000

typedef struct graphnode
{
int vexnum;
int arcnum;
int gra[MAX][MAX];
}Graph;

int dis[MAX];
int arc[MAX][MAX];

void bellman(Graph *g);

int main()
{
int i,j;
Graph *G;
G=(Graph *)malloc(sizeof(Graph));
printf("vexnum:\n");
scanf("%d",&G->vexnum);
printf("arcnum:\n");
scanf("%d",&G->arcnum);
printf("graph:\n");
for(i=0;i<G->vexnum;i++)
  for(j=0;j<G->vexnum;j++)
   scanf("%d",&G->gra[i][j]);
for(i=0;i<G->arcnum;i++)
{
  printf("the %dth arc:\n");
  scanf("%d%d",&arc[i][0],&arc[i][1]);
}
bellman(G);
return 0;
}

void bellman(Graph *G)
{
int i,j;
bool sign;
for(i=0;i<G->vexnum;i++)
  dis[i]=MAXNUM;
dis[1]=0;
sign=true;
for(i=1;i<G->vexnum;i++)
{
  sign=false;
  for(j=0;j<G->arcnum;j++)
  {
   if(dis[arc[j][0]]<MAXNUM && dis[arc[j][1]]&gt;dis[arc[j][0]]+G->gra[arc[j][0]][arc[j][1]])
   {
    dis[arc[j][1]]=dis[arc[j][0]]+G->gra[arc[j][0]][arc[j][1]];
    sign=true;
   }
  }
}
return;
}