求解带权有向图的最短路径

问题说明

一个图G=(V,E)是多段图，是指顶点集V划分成k个互不相交的子集Vi，使得E中任意一条边(u,v)必有u,v属于两个不同的子集。A是源点，E是终点。

1 动态规划

1.1 动态规划逆序解法

从后向前，E->A。next数组储存路径上一个顶点的后继节点。

#include<bits/stdc++.h>
using namespace std;
#define MAX 21
#define INF 0x3f3f3f3f //int型整数的无穷大
//问题表示
int n; //顶点个数
int start,end; //起始终止顶点编号
int c[MAX][MAX]; //边长
int next[MAX]; //最短路径上当前顶点的后继顶点
map<int, char*> vname; //存放编号对应的顶点名字
int dp[MAX]; //动态规划数组，存放f(S)结果
int Count=1; //边长计数
//初始化图
void Init()
{
 n=10, start=0, end=9;
 memset(c, INF, sizeof(c));
 for(int i=0; i<n; i++)
  dp[i]=-1;
 for(int j=0; j<n; j++)
  c[j][j]=0;
 c[0][1]=2, c[0][2]=4, c[0][3]=3;
 c[1][4]=7, c[1][5]=4;
 c[2][4]=3, c[2][5]=2, c[2][6]=4;
 c[3][4]=6, c[3][5]=2, c[3][6]=5;
 c[4][7]=3, c[4][8]=4;
 c[5][7]=6, c[5][8]=3;
 c[6][7]=3, c[6][8]=3;
 c[7][9]=3;
 c[8][9]=4;
 vname[0]="A";
 vname[1]="B1", vname[2]="B2", vname[3]="B3";
 vname[4]="C1", vname[5]="C2", vname[6]="C3";
 vname[7]="D1", vname[8]="D2";
 vname[9]="E";   
 } 
//动态规划问题逆序解法
int f(int s)
{
 if(dp[s]!=-1) return dp[s];
 if(s==end)
 {
  dp[s]=0;
  printf("(%d)f(%s)=0\n", Count++, vname[s]);
  return dp[s];
 }
 else
 {
  int cost, mincost=INF, minj;
  for(int j=0; j<n; j++)
  {
   if(c[s][j]!=0&&c[s][j]!=INF)
   {
    cost=c[s][j]+f(j);
    if(mincost>cost)
    {
     mincost=cost;
     minj=j;
    }
   }
  }
  dp[s]=mincost;
  next[s]=minj;
  printf("(%d)f(%s)=c(%s,%s)+f(%s)=%d, next(%s)=%s\n", Count++,
   vname[s], vname[s], vname[minj], vname[minj], dp[s], vname[s], vname[minj]);
  return dp[s];
 }
 }
int main()
{
 Init();
 cout<<vname[end]<<"->"<<vname[start]<<endl;
 f(start);
 cout<<"最短路径长度为"<<dp[start]<<endl;
 for(int i=start; next[i]!=0; i=next[i])
  cout<<vname[i]<<" ";
 cout<<vname[end]<<endl;
 return 0;
 } 

1.2 动态规划顺序解法

A->E

#include<bits/stdc++.h>
using namespace std;
#define MAX 21
#define INF 0x3f3f3f3f //int型整数的无穷大
//问题表示
int n; //顶点个数
int start,end; //起始终止顶点编号
int c[MAX][MAX]; //边长
int pre[MAX]; //最短路径上当前顶点的前驱顶点
map<int, char*> vname; //存放编号对应的顶点名字
int dp[MAX]; //动态规划数组，存放f(S)结果
int Count=1; //边长计数
//初始化图
void Init()
{
 n=10, start=0, end=9;
 memset(c, INF, sizeof(c));
 for(int i=0; i<n; i++)
  dp[i]=-1;
 for(int j=0; j<n; j++)
  c[j][j]=0;
 c[0][1]=2, c[0][2]=4, c[0][3]=3;
 c[1][4]=7, c[1][5]=4;
 c[2][4]=3, c[2][5]=2, c[2][6]=4;
 c[3][4]=6, c[3][5]=2, c[3][6]=5;
 c[4][7]=3, c[4][8]=4;
 c[5][7]=6, c[5][8]=3;
 c[6][7]=3, c[6][8]=3;
 c[7][9]=3;
 c[8][9]=4;
 vname[0]="A";
 vname[1]="B1", vname[2]="B2", vname[3]="B3";
 vname[4]="C1", vname[5]="C2", vname[6]="C3";
 vname[7]="D1", vname[8]="D2";
 vname[9]="E";   
 } 
//动态规划问题顺序 
int f(int s)
{
 if(dp[s]!=-1) return dp[s];
 if(s==start)
 {
  dp[s]=0;
  printf("(%d)f(%s)=0\n", Count++, vname[s]);
  return dp[s];
 }
 else
 {
  int cost, mincost=INF, mini;
  for(int i=0; i<n; i++)
  {
   if(c[i][s]!=0&&c[i][s]!=INF)
   {
    cost=c[i][s]+f(i);
    if(mincost>cost)
    {
     mincost=cost;
     mini=i;
    }
   }
  }
  dp[s]=mincost;
  pre[s]=mini;
  printf("(%d)f(%s)=c(%s,%s)+f(%s)=%d, pre(%s)=%s\n", Count++,
   vname[s], vname[s], vname[mini], vname[mini], dp[s], vname[s], vname[mini]);
  return dp[s];
 }
 }
int main()
{
 Init();
 cout<<vname[end]<<"->"<<vname[start]<<endl;
 f(end);
 return 0;
 }