《算法導論》第24章——單源最短路徑

  雖然寫這個部落客要目的是為了給我自己做一個思路記憶錄，但是如果你恰好點了進來，那麼先對你說一聲歡迎。我并不是什麼大觸，隻是一個菜菜的學生，如果您發現了什麼錯誤或者您對于某些地方有更好的意見，非常歡迎您的斧正！

最短路徑的最優子結構

最短路徑的子路徑也是最短路徑。

負權重的邊

權重為負數的邊。（我的了解：大概知道這個就可以了）

環路

最短路徑既不能包含正的環路，也不能包含負的環路。（正的環路，我覺得正常人想走最短的路，都不會在那裡打圈，除非路就是圓的；負環路你多繞幾圈，最後權重想變多小變多小，就很沒意思。）

最短路徑的表示

每個節點保持一個前驅屬性v.π，指向它的前一個結點。（這樣可以串成一串）

松弛操作

說白了就是就是檢查一下繞小路會不會更近。

v.d：表示s到v的最短路徑估計

接下來書中還有一堆性質，我就放圖，我自己也沒看，感覺很每意思，就是感覺把一些簡單的東西說的很複雜，顯得十分高大上。

24.1Bellman-Ford算法（貝爾曼-福特算法）

我的思路：

這邊為什麼要先對點循環，然後再套一個對邊的循環松弛呢？因為第一次松弛的時候，部分地方還不是最短路徑。這邊思路真的不是很好描述：最好的辦法就是自己按照它的流程走一遍！

24.2有向無環圖中的單源最短路徑問題

1、對有向無環圖進行拓撲排序

2、再進行Bellman類似操作

這一章我模棱兩可地看了看，emmm不知道它到底要講些什麼，如果你知道的話，請告訴我，謝謝！那麼我就要跳過這部分了。

24.3Dijkstra算法（迪傑斯特拉算法）

Dijkstra算法解決的是帶權重的有向圖上單源最短路徑問題，要求所有邊權重大于0 。

我的感覺：它就是一個改進的Prim算法。

我的思路：

1、每個點都有一個mark屬性标志着是否已經在路徑中

2、将邊從小排到大

3、如果點沒有全部加入到路徑中，從小到大周遊每條邊，如果邊的起點在路徑中，邊的終點沒在路徑中，就把終點的前驅設定為起點，同時終點的mark屬性變為true

4、開始重新周遊邊

24.4差分限制和最短路徑

24.5最短路徑性質的證明

四五兩章都非常的理論，我就不看了，真的很讨厭這種看的頭疼又看不懂的東西。

以下就是代碼部分了（建議粘貼到自己的編輯器中運作）

Bellman.h

#pragma once
#define BELLV 5/*點的數量*/
#define BELLE 10/*邊的數量*/

/*點*/
typedef struct BellV
{
	char data;/*資料*/
	int d;/*源結點到該點的最短距離*/
	BellV* π;/*前驅結點*/
}Bellv;
/*邊*/
typedef struct
{
	Bellv* start;/*起點*/
	Bellv* end;/*終點*/
	int w;/*權重*/
}Belle;
/*圖*/
typedef struct
{
	Bellv* v[BELLV];/*點集*/
	Belle* e[BELLE];/*邊集*/
}Bellg;

/*初始化*/
void InitBell(Bellg* &G, Bellv* root);
/*松弛操作*/
void BellRelax(Bellv* u, Bellv* v, int w);
/*Bellman算法*/
bool Bellman(Bellg* &G, Bellv* root);
/*列印路徑*/
void BellPrint(Bellv *root, Bellv *end);
/*測試函數*/
void TestBellman();
           

Bellman.cpp

#include "Bellman.h"
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

/*初始化*/
void InitBell(Bellg* &G,Bellv* root)
{
	for (int i = 0; i < BELLV; i++)
	{
		G->v[i]->d = 100;/*我們假裝這個100就是∞*/
		G->v[i]->π = NULL;/*前驅為空*/
	}
	root->d = 0;/*源結點*/
}
/*松弛操作*/
void BellRelax(Bellv* u, Bellv* v, int w)
{
	if (v->d > u->d + w)
	{
		v->d = u->d + w;
		v->π = u;
	}
}
/*Bellman算法*/
bool Bellman(Bellg* &G,Bellv* root)
{
	InitBell(G, root);
	int i, j;

	for (i = 0; i < BELLV; i++)/*對頂點進行周遊*/
	{
		if (G->v[i] != root)/*如果不是根結點*/
		{
			for (j = 0; j < BELLE; j++)
				BellRelax(G->e[j]->start, G->e[j]->end, G->e[j]->w);
		}
	}

	for (i = 0; i < BELLE; i++)/*檢測是否有負回路*/
		if (G->e[i]->end->d > G->e[i]->start->d + G->e[i]->w)
			return false;
	return true;
}
/*列印路徑*/
void BellPrint(Bellv *root, Bellv *end)
{
	Bellv* tmp = end;
	if (tmp != root)
	{
		BellPrint(root, tmp->π);
		cout << tmp->data << " ";
	}
}

/*測試函數*/
void TestBellman()
{
	/*圖*/
	Bellg* G = new Bellg();
	/*點集*/
	Bellv* s = new Bellv(); s->data = 's';
	Bellv* t = new Bellv(); t->data = 't';
	Bellv* x = new Bellv(); x->data = 'x';
	Bellv* y = new Bellv(); y->data = 'y';
	Bellv* z = new Bellv(); z->data = 'z';

	G->v[0] = s; G->v[1] = t;
	G->v[2] = x; G->v[3] = y; G->v[4] = z;

	int i;

	for (i = 0; i < BELLE; i++)
		G->e[i] = new Belle();
	G->e[0]->start = s; G->e[0]->end = t; G->e[0]->w = 6;
	G->e[1]->start = s; G->e[1]->end = y; G->e[1]->w = 7;
	G->e[2]->start = t; G->e[2]->end = x; G->e[2]->w = 5;
	G->e[3]->start = t; G->e[3]->end = y; G->e[3]->w = 8;
	G->e[4]->start = t; G->e[4]->end = z; G->e[4]->w = -4;
	G->e[5]->start = x; G->e[5]->end = t; G->e[5]->w = -2;
	G->e[6]->start = y; G->e[6]->end = x; G->e[6]->w = -3;
	G->e[7]->start = y; G->e[7]->end = z; G->e[7]->w = 9;
	G->e[8]->start = z; G->e[8]->end = s; G->e[8]->w = 2;
	G->e[9]->start = z; G->e[9]->end = x; G->e[9]->w = 7;

	Bellv* root = s;

	if (Bellman(G, root))
	{
		for (i = 0; i < BELLV; i++)
		{
			if (i != 0)
			{
				cout << root->data << " ";
				BellPrint(root, G->v[i]);
				cout << endl;
			}
		}
	}
	else
		cout << "Error!";
}
           

主函數

#include "Bellman.h"
#include <stdio.h>

int main()
{
	TestBellman();
	getchar();
	getchar();
	return 0;
}
           

運作結果

Dijstra.h

#pragma once
#define DIJV 5/*點的數量*/
#define DIJE 10/*邊的數量*/

/*點*/
typedef struct dijV
{
	char data;/*資料*/
	dijV* π;/*前驅*/
	bool mark;/*标記是否已經加入到最短路徑*/
}dijv;
/*邊*/
typedef struct
{
	dijv* start;/*起點*/
	dijv* end;/*終點*/
	int w;/*權重*/
}dije;
/*圖*/
typedef struct
{
	dijv* v[DIJV];/*點集*/
	dije* e[DIJE];/*邊集*/
}dijg;

/*比較函數*/
bool DijCmp(dije* x, dije* y);
/*Dijkstra算法*/
void Dijkstra(dijg* &g, dijv* root);
/*列印路徑*/
void DijPrint(dijv *root, dijv *end);
/*測試函數*/
void TestDijkstra();

           

Dijstra.cpp

#include "Dijstra.h"
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>/*sort排序函數所需頭檔案*/
#include<iostream>
using namespace std;


/*比較函數*/
bool DijCmp(dije* x, dije* y)
{
	return x->w < y->w;/*從小到大*/
}
/*Dijkstra算法*/
void Dijkstra(dijg* &g,dijv* root)
{
	int i, j;

	for (i = 0; i < DIJV; i++)
	{
		g->v[i]->mark = false;/*沒有被加入最短路徑中*/
		g->v[i]->π = NULL;
	}
	root->mark = true;
	sort(g->e, g->e + DIJE, DijCmp);/*按權重排序*/

	j = 0;
	while (j < DIJV - 1)/*還有點沒有被選中*/
	{
		for (i = 0; i < DIJE; i++)
		{
			if (g->e[i]->start->mark && !(g->e[i]->end->mark))/*起點在路徑中，終點沒有*/
			{
				g->e[i]->end->mark = true;
				g->e[i]->end->π = g->e[i]->start;
				j++;
				i = 20;/*結束這個for循環*/
			}
		}
	}
}
/*列印路徑*/
void DijPrint(dijv *root, dijv *end)
{
	dijv* tmp = end;
	if (tmp != root)
	{
		DijPrint(root, tmp->π);
		cout << tmp->data << " ";
	}
}
/*測試函數*/
void TestDijkstra()
{
	int i;
	dijg* g = new dijg();/*圖*/
	dijv* s = new dijv(); s->data = 's';
	dijv* t = new dijv(); t->data = 't';
	dijv* x = new dijv(); x->data = 'x';
	dijv* y = new dijv(); y->data = 'y';
	dijv* z = new dijv(); z->data = 'z';

	g->v[0] = s; g->v[1] = t;
	g->v[2] = x; g->v[3] = y; g->v[4] = z;

	for (i = 0; i < DIJE; i++)
		g->e[i] = new dije();

	g->e[0]->start = s; g->e[0]->end = t; g->e[0]->w = 10;
	g->e[1]->start = s; g->e[1]->end = y; g->e[1]->w = 5;
	g->e[2]->start = t; g->e[2]->end = x; g->e[2]->w = 1;
	g->e[3]->start = t; g->e[3]->end = y; g->e[3]->w = 2;
	g->e[4]->start = x; g->e[4]->end = z; g->e[4]->w = 4;
	g->e[5]->start = y; g->e[5]->end = t; g->e[5]->w = 3;
	g->e[6]->start = y; g->e[6]->end = x; g->e[6]->w = 9;
	g->e[7]->start = y; g->e[7]->end = z; g->e[7]->w = 2;
	g->e[8]->start = z; g->e[8]->end = s; g->e[8]->w = 7;
	g->e[9]->start = z; g->e[9]->end = x; g->e[9]->w = 6;

	dijv* root = s;
	Dijkstra(g, s);

	for (i = 0; i < DIJV; i++)
	{
		if (i != 0)
		{
			cout << root->data << " ";
			DijPrint(root, g->v[i]);
			cout << endl;
		}
	}
}
           

主函數

#include "Dijstra.h"
#include <stdio.h>

int main()
{
	TestDijkstra();
	getchar();
	getchar();
	return 0;
}
           

運作結果