C++的最短路徑怎么計(jì)算

這篇文章主要介紹“C++的最短路徑怎么計(jì)算”，在日常操作中，相信很多人在C++的最短路徑怎么計(jì)算問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C++的最短路徑怎么計(jì)算”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

最短路徑

最短路徑恐怕是圖的各種算法中最能吸引初學(xué)者眼球的了——在地圖上找一條最短的路或許每個(gè)人都曾經(jīng)嘗試過(guò)。下面我們用計(jì)算機(jī)來(lái)完成我們?cè)?jīng)的“愿望”。

在圖的算法中有個(gè)有趣的現(xiàn)象，就是問(wèn)題的規(guī)模越大，算法就越簡(jiǎn)單。圖是個(gè)復(fù)雜的結(jié)構(gòu)，對(duì)于一個(gè)特定問(wèn)題，求解特定頂點(diǎn)的結(jié)果都會(huì)受到其他頂點(diǎn)的影響——就好比一堆互相碰撞的球體，要求解特定球體的狀態(tài)，就必須考慮其他球體的狀態(tài)。既然每個(gè)頂點(diǎn)都要掃描，如果對(duì)所有的頂點(diǎn)都求解，那么算法就非常的簡(jiǎn)單——無(wú)非是遍歷嗎。然而，當(dāng)我們降低問(wèn)題規(guī)模，那很自然的，我們希望算法的規(guī)模也降低——如果不降低，不是殺雞用牛刀?但是，正是由于圖的復(fù)雜性，使得這種降低不容易達(dá)到，因此，為了降低算法的規(guī)模，使得算法就復(fù)雜了。

在下面的介紹中，清楚了印證了上面的結(jié)論。人的認(rèn)知過(guò)程是從簡(jiǎn)單到復(fù)雜，雖然表面看上去，求每對(duì)頂點(diǎn)之間的最短路徑要比特定頂點(diǎn)到其他頂點(diǎn)之間的最短路徑復(fù)雜，但是，就像上面說(shuō)的，本質(zhì)上，前者更為簡(jiǎn)單。下面的介紹沒(méi)有考慮歷史因素(就是指哪個(gè)算法先提出來(lái))，也沒(méi)有考慮算法提出者的真實(shí)想法(究竟是誰(shuí)參考了或是沒(méi)參考誰(shuí))，只是從算法本身之間的聯(lián)系來(lái)做一個(gè)闡述，如有疏漏，敬請(qǐng)?jiān)彙?/p>

準(zhǔn)備工作

一路走下來(lái)，圖類已經(jīng)很“臃腫”了，為了更清晰的說(shuō)明問(wèn)題，需要“重起爐灶另開(kāi)張”，同時(shí)也是為了使算法和儲(chǔ)存方法分開(kāi)，以便于復(fù)用。

首先要為基本圖類添加幾個(gè)接口。

template <class name, class dist, class mem>  class Network  {  public:  int find(const name& v) { int n; if (!data.find(v, n)) return -1; return n; }  dist& getE(int m, int n) { return data.getE(m, n); }  const dist& NoEdge() { return data.NoEdge; }  };  template <class name, class dist>  class AdjMatrix  {  public:  dist& getE(int m, int n) { return edge[m][n]; }  };  template <class name, class dist>  class Link  {  public:  dist& getE(int m, int n)  {  for (list::iterator iter = vertices[m].e->begin();  iter != vertices[m].e->end() && iter->vID < n; iter++);  if (iter == vertices[m].e->end()) return NoEdge;  if (iter->vID == n) return iter->cost;  return NoEdge;  }  };

然后就是為了最短路徑算法“量身定做”的“算法類”。求某個(gè)圖的最短路徑時(shí)，將圖綁定到算法上，例如這樣：

Network<char, int, Link<char, int> > a(100);  //插入點(diǎn)、邊……  Weight<char, int, Link<char, int> > b(&a);   #include "Network.h"  template <class name, class dist, class mem>  class Weight  {  public:  Weight(Network* G) : G(G), all(false), N(G->vNum())  {  length = new dist*[N]; path = new int*[N];  shortest = new bool[N]; int i, j;  for (i = 0; i < N; i++)  {  length[i] = new dist[N]; path[i] = new int[N];  }  for (i = 0; i < N; i++)  {  shortest[i] = false;  for (j = 0; j < N; j++)  {  length[i][j] = G->getE(i, j);  if (length[i][j] != G->NoEdge()) path[i][j] = i;  else path[i][j] = -1;  }  }  }  ~Weight()  {  for (int i = 0; i < N; i++) { delete []length[i]; delete []path[i]; }  delete []length; delete []path; delete []shortest;  }  private:  void print(int i, int j)  {  if (path[i][j] == -1) cout << "No Path" << endl; return;  cout << "Shortest Path: "; out(i, j); cout << G->getV(j) << endl;  cout << "Path Length: " << length[i][j] << endl;  }  void out(int i, int j)  {  if (path[i][j] != i) out(i, path[i][j]);  cout << G->getV(path[i][j]) << "->";  }  dist** length; int** path; bool* shortest; bool all; int N;  Network* G;  };

發(fā)現(xiàn)有了構(gòu)造函數(shù)真好，算法的結(jié)果數(shù)組的初始化和算法本身分開(kāi)了，這樣一來(lái)，算法的基本步驟就很容易看清楚了。

所有頂點(diǎn)之間的最短路徑(Floyed算法)

從v1到v2的路徑要么是v1->v2，要么中間經(jīng)過(guò)了若干頂點(diǎn)。顯然我們要求的是這些路徑中最短的一條。這樣一來(lái)，問(wèn)題就很好解決了——最初都是源點(diǎn)到目的點(diǎn)，然后依次添加頂點(diǎn)，使得路徑逐漸縮短，頂點(diǎn)都添加完了，算法就結(jié)束了。

void AllShortestPath()//Folyed  {  if (all) return;  for (int k = 0; k < N; k++)  {  shortest[k] = true;  for (int i = 0; i < N; i++)  for (int j = 0; j < N; j++)  if (length[i][k] + length[k][j] < length[i][j])  {  length[i][j] = length[i][k] + length[k][j];  path[i][j] = path[k][j];  }  }  all = true;  }

單源最短路徑(Dijkstra算法)

仿照上面的Floyed算法，很容易的，我們能得出下面的算法：

void ShortestPath(int v1)  {  //Bellman-Ford  for (int k = 2; k < N; k++)  for (int i = 0; i < N; i++)  for (int j = 0; j < N; j++)  if (length[v1][j] + length[j][i] < length[v1][i])  {  length[v1][i] = length[v1][j] + length[j][i];  path[v1][i] = j;  }  }

這就是Bellman-Ford算法，可以看到，采用Floyed算法的思想，不能使算法的時(shí)間復(fù)雜度從O(n3)降到預(yù)期的O(n2)，只是空間復(fù)雜度從O(n2)降到了O(n)，但這也是應(yīng)該的，因?yàn)橹恍枰瓉?lái)結(jié)果數(shù)組中的一行。因此，我并不覺(jué)得這個(gè)算法是解決“邊上權(quán)值為任意值的單源最短路徑問(wèn)題”而專門提出來(lái)的，是Dijkstra算法的“推廣”版本，他只是Floyed算法的退化版本。

顯然，F(xiàn)loyed算法是經(jīng)過(guò)N次N2條邊迭代而產(chǎn)生最短路徑的;如果我們想把時(shí)間復(fù)雜度從O(n3) 降到預(yù)期的O(n2)，就必須把N次迭代的N2條邊變?yōu)镹條邊，也就是說(shuō)每次參與迭代的只有一條邊——問(wèn)題是如何找到這條邊。

先看看邊的權(quán)值非負(fù)的情況。假設(shè)從頂點(diǎn)0出發(fā)，到各個(gè)頂點(diǎn)的距離是a1,a2……，那么，這其中的最短距離an必定是從0到n號(hào)頂點(diǎn)的最短距離。這是因?yàn)?，如果an不是從0到n號(hào)頂點(diǎn)的最短距離，那么必然是中間經(jīng)過(guò)了某個(gè)頂點(diǎn);但現(xiàn)在邊的權(quán)值非負(fù)，一個(gè)比現(xiàn)在這條邊還長(zhǎng)的邊再加上另一條非負(fù)的邊，是不可能比這條邊短的。從這個(gè)原理出發(fā)，就能得出Dijkstra算法，注意，這個(gè)和Prim算法極其相似，不知道誰(shuí)參考了誰(shuí);但這也是難免的事情，因?yàn)樗麄兊脑硎且粯拥摹?/p>

void ShortestPath(const name& vex1, const name& vex2)//Dijkstra  {  int v1 = G->find(vex1); int v2 = G->find(vex2);  if (shortest[v1]) { print(v1, v2); return; }  bool* S = new bool[N]; int i, j, k;  for (i = 0; i < N; i++) S[i] = false; S[v1] = true;  for (i = 0; i < N - 1; i++)//Dijkstra Start, like Prim?  {  for (j = 0, k = v1; j < N; j++)  if (!S[j] && length[v1][j] < length[v1][k]) k = j;  S[k] = true;  for (j = 0; j < N; j++)  if (!S[j] && length[v1][k] + length[k][j] < length[v1][j])  {  length[v1][j] = length[v1][k] + length[k][j];  path[v1][j] = k;  }  }  shortest[v1] = true; print(v1, v2);  }

如果邊的權(quán)值有負(fù)值，那么上面的原則不再適用，連帶的，Dijkstra算法也就不再適用了。這時(shí)候，沒(méi)辦法，只有接受O(n3) Bellman-Ford算法了，雖然他可以降低為O(n*e)。不過(guò)，何必讓邊的權(quán)值為負(fù)值呢?還是那句話，合理的并不好用。

特定兩個(gè)頂點(diǎn)之間的最短路徑(A*算法)

其實(shí)這才是我們最關(guān)心的問(wèn)題，我們只是想知道從甲地到乙地怎么走最近，并不想知道別的——甲地到丙地怎么走關(guān)我什么事?自然的，我們希望這個(gè)算法的時(shí)間復(fù)雜度為O(n)，但是，正像從Floyed算法到Dijkstra算法的變化一樣，并不是很容易達(dá)到這個(gè)目標(biāo)的。

讓我們先來(lái)看看Dijkstra算法求特定兩個(gè)頂點(diǎn)之間的最短路徑的時(shí)間復(fù)雜度究竟是多少。顯然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，當(dāng)S[v2]==true時(shí)，算法就可以中止了。假設(shè)兩個(gè)頂點(diǎn)之間直接的路徑是他們之間的路徑最短的(不需要經(jīng)過(guò)其他中間頂點(diǎn))，并且這個(gè)路徑長(zhǎng)度是源點(diǎn)到所有目的點(diǎn)的最短路徑中最短的，那么***次迭代的時(shí)候，就可以得到結(jié)果了。也就是說(shuō)是O(n)。然而當(dāng)兩個(gè)頂點(diǎn)的最短路徑需要經(jīng)過(guò)其他頂點(diǎn)，或者路徑長(zhǎng)度不是源點(diǎn)到未求出最短路徑的目的點(diǎn)的最短路徑中最短的，那就要再進(jìn)行若干次迭代，對(duì)應(yīng)的，時(shí)間復(fù)雜度就變?yōu)镺(2n)、O(3n)……到了***才求出來(lái)(迭代了N-1次)的就是O(n2)。

很明顯的，迭代次數(shù)是有下限的，最短路徑上要經(jīng)過(guò)多少個(gè)頂點(diǎn)，至少就要迭代多少次，我們只能使得最終的迭代次數(shù)接近最少需要的次數(shù)。如果再要減低算法的時(shí)間復(fù)雜度，我們只能想辦法把搜索范圍的O(n)變?yōu)镺(1)，這樣，即使迭代了N-1次才得到結(jié)果，那時(shí)間復(fù)雜度仍為O(n)。但這個(gè)想法實(shí)現(xiàn)起來(lái)卻是困難重重。

仍然看Dijkstra算法，***步要尋找S中的頂點(diǎn)到S外面頂點(diǎn)中最短的一條路徑，這個(gè)min運(yùn)算使用基于比較的方法的時(shí)間復(fù)雜度下限是O(longN)(使用敗者樹(shù))，然后需要掃描結(jié)果數(shù)組的每個(gè)分量進(jìn)行修改，這里的時(shí)間復(fù)雜度就只能是O(n)了。原始的Dijkstra算法達(dá)不到預(yù)期的目的。

現(xiàn)在讓我們給圖添加一個(gè)附加條件——兩點(diǎn)之間直線最短，就是說(shuō)如果v1和v2之間有直通的路徑(不經(jīng)過(guò)其他頂點(diǎn))，那么這條路徑就是他們之間的最短路徑。這樣一來(lái)，如果求的是v1能夠直接到達(dá)的頂點(diǎn)的最短路徑，時(shí)間復(fù)雜度就是O(1)了，顯然比原來(lái)***的O(n)(這里實(shí)際上是O(logN))提高了效率。

這個(gè)變化的產(chǎn)生，是因?yàn)槲覀兲砑恿恕皟牲c(diǎn)之間直線最短”這樣的附加條件，實(shí)際上就是引入一個(gè)判斷準(zhǔn)則，把原來(lái)盲目的O(n)搜索降到了O(1)。這個(gè)思想就是A*算法的思想。關(guān)于A*算法更深入的介紹，恕本人資料有限，不能滿足大家了。有興趣的可以到網(wǎng)上查查，這方面的中文資料實(shí)在太少了，大家做好看E文的準(zhǔn)備吧。

不同于現(xiàn)有的教科書(shū)，我把求最短路徑的算法的介紹順序改成了上面的樣子。我認(rèn)為這個(gè)順序才真正反映了問(wèn)題的本質(zhì)——當(dāng)減低問(wèn)題規(guī)模時(shí)，為了降低算法的時(shí)間復(fù)雜度，應(yīng)該想辦法縮小搜索范圍。而縮小搜索范圍，都用到了一個(gè)思想——盡可能的向接近***結(jié)果的方向搜索，這就是貪婪算法的應(yīng)用。

如果反向看一遍算法的演化，我們還能得出新的結(jié)論。Dijkstra算法實(shí)際上不用做n2次搜索、比較和修改，當(dāng)求出最短路徑的頂點(diǎn)后，搜索范圍已經(jīng)被縮小了，只是限于儲(chǔ)存結(jié)構(gòu)，這種范圍的縮小并沒(méi)有體現(xiàn)出來(lái)。如果我們使得這種范圍縮小直接體現(xiàn)出來(lái)，那么，用n次Dijkstra算法代替Floyed算法就能帶來(lái)效率上的提升。A*算法也是如此，如果用求n點(diǎn)的A*算法來(lái)代替Dijkstra算法，也能帶來(lái)效率的提升。

但是，每一步的進(jìn)化實(shí)際上都伴隨著附加條件的引入。從Floyed到Dijkstra是邊上的權(quán)值非負(fù)，如果這個(gè)條件不成立，那么就只能退化成Bellman-Ford算法。從Dijkstra到A*是另外的判斷準(zhǔn)則的引入(本文中是兩點(diǎn)之間直線最短)，如果這個(gè)條件不成立，同樣的，只能采用不完整的Dijkstra(求到目的頂點(diǎn)結(jié)束算法)。

到此，關(guān)于“C++的最短路徑怎么計(jì)算”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！