短鏈接生成演算法

1. 求出最短路徑，要過程，用Dijkstra演算法。。。

從v1開始遍歷
v2 = 2;
v3 = 5;
v2較小所以跳到v2
v3 = 4;

v4 = 6;
v5 = 8;
v3較小所以跳到v3
v4 = 5;
v6 = 7;
v4較小所以跳到v4
v6 = 6;
v7 = 9;
v6較小所以跳到v6
v7 = 8;

所以最後結果v1 -> v7最短路徑為v1->v2->v3->v4->v6->v7,最短路徑長度為8

2. 百度搜索引擎的演算法是怎樣的

衡量網頁質量的維度
網路搜索引擎在衡量網頁質量時，會從以下三個維度綜合考慮給出一個質量打分。下面會一一介紹這些影響網頁質量判斷的維度特徵：
• 內容質量
• 瀏覽體驗
• 可訪問性
一個訪問流暢，內容質量高且瀏覽體驗好的網頁具有較高的質量；反之，任何一個維度出現問題，都會影響網頁的整體質量。下面我們具體介紹下這三個維度。

衡量網頁質量的維度——內容質量

網頁主體內容是網頁的價值所在，是滿足用戶需求的前提基礎。網路搜索引擎評價網頁內容質量主要看其主體內容的好壞，以及主體內容是否可以讓用戶滿意。 不同類型網頁的主體內容不同，網路搜索引擎判斷不同網頁的內容價值時，需要關注的點也有區別，如：
• 首頁：導航鏈接和推薦內容是否清晰、有效。
• 文章頁：能否提供清晰完整的內容，圖文並茂更佳。
• 商品頁：是否提供了完整真實的商品信息和有效的購買入口。
• 問答頁：是否提供了有參考價值的答案。
• 下載頁：是否提供下載入口，是否有許可權限制，資源是否有效。
• 文檔頁：是否可供用戶閱讀，是否有許可權限制。
• 搜索結果頁：搜索出來的結果是否與標題相關。

網路搜索引擎考量網頁內容質量的維度非常多，最為重要的是：成本；內容完整；信息真實有效以及安全。下面我們通過舉例來感受一下網路搜索引擎是如何對網頁的內容質量進行分類的，請站長對比自己站點的頁面，站在搜索引擎和用戶的角度為自己打分：
1、內容質量好：
網路搜索引擎認為內容質量好的網頁，花費了較多時間和精力編輯，傾注了編者的經驗和專業知識；內容清晰、完整且豐富；資源有效且優質；信息真實有效；安全無毒；不含任何作弊行為和意圖，對用戶有較強的正收益。對這部分網頁，網路搜索引擎會提高其展現在用戶面前的機率。例如：
• 專業醫療機構發布的內容豐富的醫療專題頁面；
• 資深工程師發布的完整解決某個技術問題的專業文章；
• 專業視頻網站上，播放清晰流暢的正版電影或影視全集頁面；
• 知名B2C網站上，一個完整有效的商品購買頁；
• 權威新聞站原創或經過編輯整理的熱點新聞報道；
• 經過網友認真編輯，內容豐富的詞條；
• 問答網站內，回答的內容可以完美解決提問者的問題。

實例參考：

示例

內容質量

說明

case 3.1.1-1

好

專業醫療網站發布的豐富醫療專題頁面

case 3.1.1-2

好

資深工程師發布的完整解決某個技術問題的專業文章

case 3.1.1-3

好

專業視頻網站上，播放清晰流暢的正版影視全集頁面

case 3.1.1-4

好

京東的一個完整有效的商品購買頁

case 3.1.1-5

好

權威新聞站原創的熱點新聞的報道

case 3.1.1-6

好

經過網友認真編輯，內容豐富的網路詞條

case3.1.1-7

好

網路知道上，完美解決用戶問題的問答頁

2、內容質量中：
內容質量中等的網頁往往能滿足用戶需求，但未花費較多時間和精力進行製作編輯，不能體現出編者的經驗和專業知識；內容完整但並不豐富；資源有效但質量欠佳；信息雖真實有效但屬採集得來；安全無毒；不含作弊行為和意圖。在互聯網中，中等質量網頁其實是一個比較大的數量集合，種類面貌也繁雜多樣，網路搜索引擎在評價這類網頁時往往還要考慮其它非常多因素。在這里，我們僅部分舉例來讓各位感受一下：
• 論壇類網站里一個普通的帖子；
• 一個普通的問答網頁；
• 沒有進行任何編輯，直接轉載其它網站的新聞；
• 無版權信息的普通電影播放頁
• 採集知名小說網站的盜版小說頁。

實例參考：

示例

內容質量

說明

case 3.1.2-1

中

網易直接轉載了中國新聞網的一篇新聞。

case 3.1.2-2

中

文庫上網友上傳的「國慶放假安排」新聞

case 3.1.2-3

中

採集起點小說網的盜版小說站

case 3.1.2-4

中

網路貼吧里一個普通的帖子

3、內容質量差：
網路搜索引擎認為主體內容信息量較少，或無有效信息、信息失效過期的都屬於內容質量差網頁，對用戶沒有什麼實質性的幫助，應該減少其展現的機會。同時，如果一個網站內該類網頁的佔比過大，也會影響網路搜索引擎對站點的評級，尤其是UGC網站、電商網站、黃頁網站要尤其重視對過期、失效網頁的管理。例如：
• 已下架的商品頁，或已過期的團購頁；
• 已過有效期的招聘、交易頁面；
• 資源已失效，如視頻已刪除、軟體下載後無法使用等。

4、沒有內容質量可言：
沒有內容質量可言的網頁指那些製作成本很低，粗製濫造；從別處採集來的內容未經最起碼的編輯整理即放置線上；掛木馬等病毒；含有作弊行為或意圖；完全不能滿足用戶需求，甚至含有欺騙內容的網頁。例如：
• 內容空短，有很少量的內容，卻不能支撐頁面的主要意圖；
• 問答頁有問無答，或回答完全不能解決問題；
• 站內搜索結果頁，但沒有給出相關信息

除上述網頁外，欺騙用戶和搜索引擎的網頁在無內容質量可言集合里占很高比例。網路搜索引擎對作弊網頁的定義是：不以滿足用戶需求為目的，通過不正當手段欺騙用戶和搜索引擎從而獲利的網頁。目前互聯網上這部分網頁還屬少數，但作弊網頁的價值是負向的，對用戶的傷害非常大，對這類網頁，搜索引擎持堅決打擊態度。

衡量網頁質量的維度——瀏覽體驗
不同質量的網頁帶給用戶的瀏覽體驗會有很大差距，一個優質的網頁給用戶的瀏覽體驗應該是正向的。用戶希望看到干凈、易閱讀的網頁，排版混亂、廣告過多會影響用戶對網頁主體內容的獲取。在網路搜索引擎網頁質量體系中，用戶對網頁主體內容的獲取成本與瀏覽體驗呈反比，即獲取成本越高，瀏覽體驗越低。面對內容質量相近的網頁，瀏覽體驗佳者更容易獲得更高的排位，而對於瀏覽體驗差的網頁，網路搜索引擎會視情況降低其展現的機率甚至拒絕收錄。
影響用戶瀏覽體驗好壞的因素很多，目前網路搜索引擎主要從內容排版、廣告影響兩方面對網頁進行考量：
內容排版：用戶進入網頁第一眼看到的就是內容排版，排版決定了用戶對網頁的第一印象，也決定了用戶對內容獲取的成本。
廣告影響：網路搜索引擎理解網站的生存發展需要資金支持，對網頁上放置正當廣告持支持態度。網頁應該以滿足用戶需求為主旨，最佳狀態即「主體內容與廣告一起滿足用戶需求，內容為主，廣告為輔」，而不應讓廣告成為網頁主體。

下面我們通過舉例來感受一下網路搜索引擎是如何對網頁的瀏覽體驗進行分類的，站長可以據此對比檢驗自己站點的瀏覽體驗如何：
1、瀏覽體驗好：
頁面布局合理，用戶獲取主體內容成本低，一般具有以下特徵：
• 排版合理，版式美觀，易於閱讀和瀏覽；
• 用戶需要的內容占據網頁最重要位置；
• 能夠通過頁面標簽或頁面布局十分清楚地區分出哪些是廣告；
• 廣告不搶佔主體內容位置，不阻礙用戶對主要內容的獲取；

實例參考：

示例

瀏覽體驗

說明

case 3.2.1-1

好

招聘、房產等網站首頁也有很多廣告，但都是招聘相關的，瀏覽體驗是ok的。

case 3.2.1-2

好

文章頁，頁面布局合理，無廣告，排版好，結構合理

case 3.2.1-3

好

游戲首頁，排版美觀，布局合理，無廣告，瀏覽體驗優

2、瀏覽體驗差：
頁面布局和廣告放置影響了用戶對主體內容的獲取，提高了用戶獲取信息的成本，令用戶反感。包括但不僅限於以下情況：
• 正文內容不換行或不分段，用戶閱讀困難；
• 字體和背景顏色相近，內容辨別困難；
• 頁面布局不合理，網頁首屏看不到任何有價值的主體內容；
• 廣告遮擋主體內容；或者在通用解析度下，首屏都是廣告，看不到主體內容；
• 彈窗廣告過多；
• 影響閱讀的浮動廣告過多
• 點擊鏈接時，出現預期之外的彈窗；
• 廣告與內容混淆，不易區分；

衡量網頁質量的維度——可訪問性
用戶希望快速地從搜索引擎獲取到需要的信息，網路搜索引擎盡可能為用戶提供能一次性直接獲取所有信息的網頁結果。網路搜索引擎認為不能直接獲取到主體內容的網頁對用戶是不友好的，會視情況調整其展現機率。

網路搜索引擎會從正常打開、許可權限制、有效性三方面判斷網頁的可訪問性，對於可以正常訪問的網頁，可以參與正常排序；對於有許可權限制的網頁，再通過其它維度對其進行觀察；對於失效網頁，會降權其展現機制甚至從資料庫中刪除。

1、可正常訪問的網頁
無許可權限制，能直接訪問所有主體內容的網頁。

2、有許可權限制的網頁
此類網頁分為兩種：打開許可權和資源獲取許可權
1）打開許可權：指打開網頁都需要登錄許可權，沒有許可權完全無法看到具體內容，普通用戶無法獲取或獲取成本很高，網路搜索引擎會降低其展現機率。不包括以登錄為主要功能的網頁。
2）資源獲取許可權：指獲取網頁主要內容，如文檔、軟體、視頻等，需要許可權或者需要安裝插件才能獲得完整內容。此時會分三種情況：
• 提供優質、正版內容的網站，由於內容建設成本很高，盡管查看全文或下載時需要許可權或安裝插件，但屬於用戶預期之內，網路搜索引擎也不認為許可權行為對用戶造成傷害，給予與正常可訪問頁面相同的對待。
• 對於一些非優質、非正版的資源，來自於用戶轉載甚至機器採集，本身成本較低，內容也不獨特，用戶獲取資源還有許可權限制——需要用戶注冊登錄或者付費查看，網路搜索引擎會根據具體情況決定是否調整其展現。
• 還有一些視頻、下載資源頁，也許自身資源質量並不差，但需要安裝非常冷門的插件才能正常訪問，比如要求安裝「xx大片播放器」，網路搜索引擎會懷疑其有惡意傾向。

實例參考：

示例

可訪問性

說明

case 3.2-1

好

CNKI上的一篇論文，收費才能下載，但有版權，瀏覽體驗好

case 3.2-2

好

優酷上一部新電影，需要付費才能觀看，瀏覽體驗好。

case 3.2-3

中

內容是來，但是需要登錄才能看更多

case 3.2-4

差

入黨申請書，本身就是轉載的，網上到處都是，但這個頁面仍然要求收費才能下載。

3、失效網頁
往往指死鏈和主體資源失效的網頁。網路搜索引擎認為這部分網頁無法提供有價值信息，如果站點中此類網頁過多，也會影響網路搜索引擎對其的收錄和評級。建議站長對此類網頁進行相應設置，並及時登錄網路站長平台，使用死鏈提交工具告知網路搜索引擎。
失效網頁包括但不僅限於：
• 404、403、503等網頁；
• 程序代碼報錯網頁；
• 打開後提示內容被刪除，或因內容已不存在跳轉到首頁的網頁；
• 被刪除內容的論壇帖子，被刪除的視頻頁面（多出現在UGC站點）

具體請參閱《網路搜索引擎網頁質量白皮書》，望採納！

3. djstl演算法

定義Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,
CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。
問題描述在無向圖
G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）

編輯本段迪傑斯特拉演算法迪傑斯特拉(Dijkstra)演算法思想
按路徑長度遞增次序產生最短路徑演算法：

把V分成兩組：

（1）S：已求出最短路徑的頂點的集合

（2）V-S=T：尚未確定最短路徑的頂點集合

將T中頂點按最短路徑遞增的次序加入到S中，

保證：（1）從源點V0到S中各頂點的最短路徑長度都不大於

從V0到T中任何頂點的最短路徑長度

（2）每個頂點對應一個距離值

S中頂點：從V0到此頂點的最短路徑長度

T中頂點：從V0到此頂點的只包括S中頂點作中間

頂點的最短路徑長度

依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的

直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和

（反證法可證）

求最短路徑步驟
演算法步驟如下：

1. 初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值

若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值

若不存在<V0,Vi>，d(V0,Vi)為∝

2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S

3. 對S中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的

距離值縮短，則修改此距離值

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

編輯本段迪傑斯特拉演算法的原理首先，引進一個輔助向量D，它的每個分量D表示當前所找到的從始點v到每個終點vi的最短路徑的長度。如D[3]=2表示從始點v到終點3的路徑相對最小長度為2。這里強調相對就是說在演算法過程中D的值是在不斷逼近最終結果但在過程中不一定就等於最短路徑長度。它的初始狀態為：若從v到vi有弧，則D為弧上的權值；否則置D為∞。顯然，長度為
D[j]=Min{D | vi∈V} 的路徑就是從v出發的長度最短的一條最短路徑。此路徑為(v,vj)。
那麼，下一條長度次短的最短路徑是哪一條呢？假設該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]和從vj到vk的弧上的權值之和。
一般情況下，假設S為已求得最短路徑的終點的集合，則可證明：下一條最短路徑（設其終點為X）或者是弧(v,x)，或者是中間只經過S中的頂點而最後到達頂點X的路徑。因此，下一條長度次短的最短路徑的長度必是D[j]=Min{D
| vi∈V-S} 其中，D或者是弧(v,vi)上的權值，或者是D[k](vk∈S)和弧(vk,vi)上的權值之和。 迪傑斯特拉演算法描述如下：
1）arcs表示弧上的權值。若不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到從v出發的最短路徑的終點的集合，初始狀態為空集。那麼，從v出發到圖上其餘各頂點vi可能達到的最短路徑長度的初值為D=arcs[Locate
Vex(G,v),i] vi∈V 2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發到集合V-S上任一頂點vk可達的最短路徑長度。

編輯本段迪傑斯特拉演算法C#程序public class Edge

{

public string StartNodeID ;

public string EndNodeID ;

public double Weight ; //權值，代價

} 節點則抽象成Node類，一個節點上掛著以此節點作為起點的「出邊」表。

public class Node

{

private string iD ;

private ArrayList edgeList ;//Edge的集合－－出邊表

public Node(string id )

{

this.iD = id ;

this.edgeList = new ArrayList() ;

}

property#region property

public string ID

{

get

{

return this.iD ;

}

}

public ArrayList EdgeList

{

get

{

return this.edgeList ;

}

}

#endregion

}

在計算的過程中，我們需要記錄到達每一個節點權值最小的路徑，這個抽象可以用PassedPath類來表示：

/// <summary>

/// PassedPath 用於緩存計算過程中的到達某個節點的權值最小的路徑

/// </summary>

public class PassedPath

{

private string curNodeID ;

private bool beProcessed ; //是否已被處理

private double weight ; //累積的權值

private ArrayList passedIDList ; //路徑

public PassedPath(string ID)

{

this.curNodeID = ID ;

this.weight = double.MaxValue ;

this.passedIDList = new ArrayList() ;

this.beProcessed = false ;

}

#region property

public bool BeProcessed

{

get

{

return this.beProcessed ;

}

set

{

this.beProcessed = value ;

}

}

public string CurNodeID

{

get

{

return this.curNodeID ;

}

}

public double Weight

{

get

{

return this.weight ;

}

set

{

this.weight = value ;

}

}

public ArrayList PassedIDList

{

get

{

return this.passedIDList ;

}

}

#endregion

}

另外，還需要一個表PlanCourse來記錄規劃的中間結果，即它管理了每一個節點的PassedPath。

/// <summary>

/// PlanCourse 緩存從源節點到其它任一節點的最小權值路徑=》路徑表

/// </summary>

public class PlanCourse

{

private Hashtable htPassedPath ;

#region ctor

public PlanCourse(ArrayList nodeList ,string originID)

{

this.htPassedPath = new Hashtable() ;

Node originNode = null ;

foreach(Node node in nodeList)

{

if(node.ID == originID)

{

originNode = node ;

}

else

{

PassedPath pPath = new PassedPath(node.ID) ;

this.htPassedPath.Add(node.ID ,pPath) ;

}

}

if(originNode == null)

{

throw new Exception("The origin node is not exist !")
;

}

this.InitializeWeight(originNode) ;

}

private void InitializeWeight(Node originNode)

{

if((originNode.EdgeList == null)
||(originNode.EdgeList.Count == 0))

{

return ;

}

foreach(Edge edge in originNode.EdgeList)

{

PassedPath pPath = this[edge.EndNodeID] ;

if(pPath == null)

{

continue ;

}

pPath.PassedIDList.Add(originNode.ID) ;

pPath.Weight = edge.Weight ;

}

}

#endregion

public PassedPath this[string nodeID]

{

get

{

return (PassedPath)this.htPassedPath[nodeID] ;

}

}

}

在所有的基礎構建好後，路徑規劃演算法就很容易實施了，該演算法主要步驟如下：

(1)用一張表(PlanCourse)記錄源點到任何其它一節點的最小權值，初始化這張表時，如果源點能直通某節點，則權值設為對應的邊的權，否則設為double.MaxValue。

(2)選取沒有被處理並且當前累積權值最小的節點TargetNode，用其邊的可達性來更新到達其它節點的路徑和權值（如果其它節點
經此節點後權值變小則更新，否則不更新），然後標記TargetNode為已處理。

(3)重復(2)，直至所有的可達節點都被處理一遍。

(4)從PlanCourse表中獲取目的點的PassedPath，即為結果。

下面就來看上述步驟的實現，該實現被封裝在RoutePlanner類中：

/// <summary>

/// RoutePlanner 提供圖演算法中常用的路徑規劃功能。

/// 2005.09.06

/// </summary>

public class RoutePlanner

{

public RoutePlanner()

{

}

#region Paln

//獲取權值最小的路徑

public RoutePlanResult Paln(ArrayList nodeList ,string
originID ,string destID)

{

PlanCourse planCourse = new PlanCourse(nodeList
,originID) ;

Node curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;

#region 計算過程

while(curNode != null)

{

PassedPath curPath = planCourse[curNode.ID] ;

foreach(Edge edge in curNode.EdgeList)

{

PassedPath targetPath = planCourse[edge.EndNodeID] ;

double tempWeight = curPath.Weight + edge.Weight ;

if(tempWeight < targetPath.Weight)

{

targetPath.Weight = tempWeight ;

targetPath.PassedIDList.Clear() ;

for(int i=0 ;i<curPath.PassedIDList.Count ;i++)

{

targetPath.PassedIDList.Add(curPath.PassedIDList.ToString())
;

}

targetPath.PassedIDList.Add(curNode.ID) ;

}

}

//標志為已處理

planCourse[curNode.ID].BeProcessed = true ;

//獲取下一個未處理節點

curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;

}

#endregion

//表示規劃結束

return this.GetResult(planCourse ,destID) ;

}

#endregion

#region private method

#region GetResult

//從PlanCourse表中取出目標節點的PassedPath，這個PassedPath即是規劃結果

private RoutePlanResult GetResult(PlanCourse
planCourse ,string destID)

{

PassedPath pPath = planCourse[destID] ;

if(pPath.Weight == int.MaxValue)

{

RoutePlanResult result1 = new RoutePlanResult(null
,int.MaxValue) ;

return result1 ;

}

string[] passedNodeIDs = new
string[pPath.PassedIDList.Count] ;

for(int i=0 ;i<passedNodeIDs.Length ;i++)

{

passedNodeIDs = pPath.PassedIDList.ToString() ;

}

RoutePlanResult result = new
RoutePlanResult(passedNodeIDs ,pPath.Weight) ;

return result ;

}

#endregion

#region GetMinWeightRudeNode

//從PlanCourse取出一個當前累積權值最小，並且沒有被處理過的節點

private Node GetMinWeightRudeNode(PlanCourse
planCourse ,ArrayList nodeList ,string originID)

{

double weight = double.MaxValue ;

Node destNode = null ;

foreach(Node node in nodeList)

{

if(node.ID == originID)

{

continue ;

}

PassedPath pPath = planCourse[node.ID] ;

if(pPath.BeProcessed)

{

continue ;

}

if(pPath.Weight < weight)

{

weight = pPath.Weight ;

destNode = node ;

}

}

return destNode ;

}

#endregion

#endregion

}

編輯本段迪傑斯特拉演算法pascal程序type bool=array[1..10]of
boolean;

arr=array[0..10]of integer;

var a:array[1..10,1..10]of integer;
//存儲圖的鄰接數組，無邊為10000

c,d,e:arr; //c為最短路徑數值,d為各點前趨,

t:bool; //e：路徑，t為輔助數組

i,j,n,m:integer;

inf,outf:text;

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

procere init; //不同題目鄰接數組建立方式不一樣

begin

assign(inf,'dijkstra.in');
assign(outf,'dijkstra.out');

reset(inf); rewrite(outf);

read(inf,n);

for i:=1 to n do

for j:=1 to n do

begin

read(inf,a[i,j]);

if a[i,j]=0 then a[i,j]:=10000;

end;

end;

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

procere dijkstra(qi:integer; t:bool; var c{,d}:arr);
//qi起點，{}中為求路徑部

var i,j,k,min:integer; //分,不需求路徑時可以不要

begin //t數組一般在調用前初始

t[qi]:=true; //化成false,也可將部分點

{for i:=1 to n do d[i]:=qi; d[qi]:=0; }
//初始化成true以迴避這些點

for i:=1 to n do c[i]:=a[qi,i];

for i:=1 to n-1 do

begin

min:=10001;

for j:=1 to n do

if (c[j]<min)and(not(t[j])) then begin k:=j;
min:=c[j];end;

t[k]:=true;

for j:=1 to n do

if (c[k]+a[k,j]<c[j])and(not(t[j])) then

begin

c[j]:=c[k]+a[k,j]; {d[j]:=k;}

end;

end;

end;

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

procere make(zh:integer; d:arr; var e:arr);
//生成路徑,e[0]保存路徑

var i,j,k:integer; //上的節點個數

begin

i:=0;

while d[zh]<>0 do

begin

inc(i);e[i]:=zh;zh:=d[zh];

end;

inc(i);e[i]:=qi; e[0]:=I;

end;

主程序調用：求最短路徑長度：初始化t，然後dijkstra(qi,t,c,d)

求路徑：make(m,d,e) ，m是終點

編輯本段Dijkstra演算法的堆優化(PASCAL實現)一、思考
我們可以發現，在實現步驟時，效率較低(需要O(n)，使總復雜度達到O(n^2)。對此可以考慮用堆這種數據結構進行優化，使此步驟復雜度降為O(log(n))(總復雜度降為O(n
log(n))。

二、實現
1. 將與源點相連的點加入堆，並調整堆。
2. 選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。
3. 處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點
1):若該點在堆里，更新距離，並調整該元素在堆中的位置。
2):若該點不在堆里，加入堆，更新堆。
4. 若取到的u為終點，結束演算法；否則重復步驟2、3。
三、代碼
procere Dijkstra;

var

u,v,e,i:longint;

begin

fillchar(dis,sizeof(dis),$7e); //距離

fillchar(Inh,sizeof(Inh),false); //是否在堆中

fillchar(visit,sizeof(visit),false); //是否訪問過

size:=0;

e:=last[s];

while e<>0 do //步驟1

begin

u:=other[e];

if not(Inh[u]) then //不在堆里

begin

inc(size);

heap[size]:=u;

dis[u]:=cost[e];

Loc[u]:=size; //Loc數組記錄元素在堆中的位置

Inh[u]:=true;

Shift_up(Loc[u]); //上浮

end

else

if cost[e]<dis[u] then //在堆里

begin

dis[u]:=cost[e];

Shift_up(Loc[u]);

Shift_down(Loc[u]);

end;

e:=pre[e];

end;

visit[s]:=true;

while true do

begin

u:=heap[1]; //步驟2

if u=t then break; //步驟4

visit[u]:=true;

heap[1]:=heap[size];

dec(size);

Shift_down(1);

e:=last[u];

while e<>0 do //步驟3

begin

v:=other[e];

if Not(visit[v]) and (dis[u]+cost[e]<dis[v]) then
//與u相鄰的，未被訪問過的，滿足三角不等式的頂點

if Inh[v] then //在堆中

begin

dis[v]:=dis[u]+cost[e];

Shift_up(Loc[v]);

Shift_Down(Loc[v]);

end

else //不再堆中

begin

inc(size);

heap[size]:=v;

dis[v]:=dis[u]+cost[e];

Loc[v]:=size;

Inh[v]:=true;

Shift_up(Loc[v]);

end;

e:=pre[e];

end;

end;

writeln(dis[t]);

end;
http://ke..com/view/7839.htm

http://ke..com/view/1939816.htm

4. sh實現最小生成樹和最短路徑的演算法

圖的最小生成樹與最短路徑的演算法

一、圖的生成樹與最小生成樹
在一個連通圖G中，如果取它的全部頂點和一部分邊構成一個子圖G』，即：

若邊集E（G』）中的邊既將圖中的所有頂點連通又不形成迴路，則稱子圖G』是原圖G的一棵生成樹。
最小生成樹：給圖中每個邊賦一權值，所有生成樹中所選擇邊的權值之和最小的生成樹，稱之為最小代價生成樹，即是最小生成樹。

1、普里姆演算法
1.1演算法描述
假設G=（V, E）是一個具有n個頂點的連通網，T=（U, TE）是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，U和TE的初值均為空集。演算法開始時，首先從V中任取一個頂點（假定取v1），將它並入U中，此時U={v1}，然後只要U是V的真子集（即），就從那些其一個端點已在T中，另一個端點仍在T外的所有邊中，找一條最短（即權值最小）邊，假定為（vi, vj），其中，並把該邊（vi, vj）和頂點vj分別並入T的邊集TE和頂點集U，如此進行下去，每次往生成樹里並入一個頂點和一條邊，直到（n-1）次後就把所有n個頂點都並入到生成樹T的頂點集中，此時U＝V，TE中含有（n-1）條邊，T就是最後得到的最小生成樹。 1.2關鍵問題
普里姆演算法的關鍵之處是：每次如何從生成樹T中到T外的所有邊中，找出一條最短邊。例如，在第k次前，生成樹T中已有k個頂點和（k-1）條邊，此時T中到T外的所有邊數為k（n-k），當然它包括兩頂點間沒有直接邊相連，其權值被看作為「無窮大」的邊在內，從如此多的邊中查找最短邊，其時間復雜性為O（k（n-k）），顯然是很費時的。是否有一種好的方法能夠降低查找最短邊的時間復雜性呢？ 1.3 解決方法
方法是：假定在進行第k次前已經保留著從T中到T外每一頂點（共（n-k）個頂點）的各一條最短邊，進行第k次時，首先從這（n-k）條最短邊中，找出一條最最短的邊（它就是從T中到T外的所有邊中的最短邊），假設為（vi, vj），此步需進行（n-k）次比較；然後把邊（vi, vj）和頂點vj分別並入T中的邊集TE和頂點集U中，此時T外只有n-（k+1）個頂點，對於其中的每個頂點vt，若（vj, vt）邊上的權值小於已保留的從原T中到vt的最短邊的權值，則用（v, vt）修改之，使從T中到T外頂點vt的最短邊為（vj, vt），否則原有最短邊保持不變，這樣，就把第k次後從T中到T外每一頂點vt的各一條最短邊都保留下來了。為進行第（k+1）次運算做好了准備，此步需進行（n-k-1）次比較。所以，利用此方法求第k次的最短邊共需比較2（n-k）-1次，即時間復雜性為O（n-k）。
1.4 prim演算法：
設一個輔助數組closedge，以記錄從U到V—U具有最小代價的邊。數組中的每個元素closedge[v]是記錄類型，包含兩個域： closedge[v].lowcast=Min{cost(u,v)|u∈U}; closedge[v].vex存儲該邊依附的在U中的頂點。
proc mintree_prim(gn:adjmatrix;u0:integer);
begin
for v:=1 to n do
if v<>u0 then
with closedage[v] do [vex:=u0; lowcast:=gn[u0,v];]
closedge[u0].lowcast:=0;{並入U集合}
for i:=1 to n-1 do
begin
v:=min(closedge);{尋找代價最小的邊}
write(closedge[v].vex,v); closedge[v].lowcast:=0;{並入U集合}
for k:=1 to n do
if gn[v,k]<closedge[k].lowcast then
begin closedge[k].lowcast:=gn[v,k]; closedge[k].vex:=v; end;
end;
end; 練習1：prim演算法實現
【問題描述】從文件中讀入連通帶權圖的信息，按prim演算法求出該圖的最小生成樹，以V1作為初始結點。
【輸入文件】第一行兩個整數m和n，分別表示圖的結點數和圖中的邊數。以下n行表示n條邊：每一行三個數x、y和k，k表示x與y之間邊的權值。
【輸出文件】共m行，第一行：最小生成樹的權；以下m-1行表示選取的邊，邊的第1個結點小於第2個結點，並按結點由小到大輸出。
【示例】輸入：5 7 輸出：45
1 2 17 1 4
2 3 30 1 5
1 4 5 2 4
2 4 10 3 5
3 4 24
3 5 7
1 5 23

練習2： Eddy painting
Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result it can be imagined, the friends are not interested in his picture.Eddy feels very puzze,in order to change all friends 's view to his technical of painting pictures ,so Eddy creates a problem for the his friends of you.
Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally to link in the same place. How many distants does your ty discover the shortest length which the ink draws?
Input：
The first line contains 0 < n <= 100, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point.

Input contains multiple test cases. Process to the end of file.
Output：
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the points.
Sample Input：
3
1.0 1.0
2.0 2.0
2.0 4.0
Sample Output：
3.41

2、克魯斯卡爾演算法
2.1 演算法描述
假設G＝（V，E）是一個具有n個頂點的連通網，T＝（U，TE）是G的最小生成樹，U的初值等於V，即包含有G中的全部頂點，TE的初值為空。此演算法的基本思想是，將圖G中的邊按權值從小到大的順序依次選取，若選取的邊使生成樹T不形成迴路，則把它並入TE中，保留作為T的一條邊，若選取的邊使生成樹T形成迴路，則將其舍棄，如此進行下去，直到TE中包含有n-1條邊為止。此時的T即為最小生成樹。
2.2 關鍵問題
克魯斯卡爾演算法的關鍵之處是：如何判斷欲加入的一條邊是否與生成樹中已選取的邊形成迴路。這可將各頂點劃分為所屬集合的方法來解決，每個集合中的頂點表示一個無迴路的連通分量。演算法開始時，由於生成樹的頂點集等於圖G的頂點集，邊集為空，所以n個頂點分屬於n個集合。每個集合中只有一個頂點，表明頂點之問互不連通。
2.3 Kruskal演算法：
proc mintree_krusk(gn:adjmatrix);
begin
for i:=1 to n do
un[i]:=i;
for i:=1 to n-1 do
begin
minedge(a,b);
write(a,b,gn[a,b]);
k:=un[b];
for i:=1 to n do {兩個連通分量合並}
if un[i]=k then un[i]:=un[a];
end;
end;
2.4 注意：
proc minedge(var a:integer;var b:integer);用於在剩下的邊中選取不再同一連通分量上的最小代價的邊，邊的結點分別為a和b。
為了實現該過程，可以將圖中的邊生成一邊結點（包含兩個頂點和代價）數組，由小到大排序，然後通過排序後的數組進行處理；
un數組：用來記載隨著邊的加入，各頂點屬於哪個連通分量。
練習3：Kruskal演算法實現
【問題描述】從文件中讀入連通帶權圖的信息，按Kruskal演算法求出該圖的最小生成樹，以V1作為初始結點。
【輸入文件】第一行兩個整數m和n，分別表示圖的結點數和圖中的邊數。以下n行表示n條邊：每一行三個數x、y和k，k表示x與y之間邊的權值。
【輸出文件】共m行，第一行：最小生成樹的權；以下m-1行表示選取的邊，按選取邊的權值由小到大輸出。
【示例】輸入：5 7 輸出：45
1 2 17 1 4
2 3 30 3 5
1 4 5 2 4
2 4 10 1 5
3 4 24
3 5 7
1 5 23

練習4：判斷最小生成樹是否唯一
Given a connected undirected graph, tell if its minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:
1. V' = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.
Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!

二、最短路徑
【問題描述】由於從一頂點到另一頂點可能存在著多條路徑。每條路徑上所經過的邊數可能不同，即路徑長度不同，我們把路徑長度最短（即經過的邊數最少）的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。求圖中一頂點vi到其餘各頂點的最短路徑和最短距離比較容易，只要從該頂點vi，出發對圖進行一次廣度優先搜索遍歷，在遍歷時記下每個結點的層次即可。
若圖是帶權圖（假定權值非負）從源點vi到終點vj的每條路徑上的權（它等於該路徑上所經邊上的權值之和，稱為該路徑的帶權路徑長度）可能不同，我們把權值最小的那條路徑也稱做最短路徑，其權值也稱作最短路徑長度或最短距離。
實際上，這兩類最短路徑問題可合並為一類，這只要把第一類的每條邊的權都設為1就歸屬於第二類了，所以在以後的討論中，若不特別指明，均是指第二類的最短路徑問題。
求圖的最短路徑問題包括兩個子問題：一是求圖中一頂點到其餘各頂點的最短路徑，二是求圖中每對頂點之間的最短路徑。下面分別進行討論。
始點 終點 最短路徑 路徑長度
v0 v1 No path
v2 (v0,v2) 10
v3 (v0,v4,v3) 50
v4 (v0,v4) 30
v5 (v0,v4,v3,v5) 60

始點 終點 最短路徑 路徑長度
v1 V2 (v1,v2) 10
V3 (v1,v2,v3) 27
V4 (v1,v5,v4) 20
v5 (v1,v5) 7

1、從一頂點到其餘各頂點的最短路徑
1.1 描述
迪傑斯特拉（Dijkstra）於1959年提出了解決此問題的一般演算法，具體做法是按照從源點到其餘每一頂點的最短路徑長度的升序依次求出從源點到各頂點的最短路徑及長度，每次求出從源點vi到一個終點vj的最短路徑及長度後，都要以vj作為新考慮的中間點，用vi到vj的最短路徑和最短路徑長度對vi到其它尚未求出最短路徑的那些終點的當前路徑及長度作必要的修改，使之成為當前新的最短路徑和最短路徑長度，當進行n-2次後演算法結束。
1.2 Dijkstra演算法:
首先，引進一個輔助向量dist，dist[i]表示當前所找到的從始點V到每個終點Vi的最短路徑長度。其初態為：若<v,vi>存在，則dist[i]為其上的權值，否則為最大值（計算機能表示）。
演算法:(1)用鄰接矩陣cost表示帶權有向圖。S表示已找到的從v出發的最短路徑的終點的集合，初態為空。dist向量的初值為：dist[v,i]=cost[v,i];
(2)選擇vj，使得：dist[j]=Min{dist[i]|vi∈V-S}；vj就是當前求得從v出發的最短路徑的終點。
S=S+{j};
(3)修改從v出發到集合V-S上任意頂點vk可達的最短路徑長度。
if dist[j]+cost[j,k]<dist[k] then dist[k]:=dist[j]+cost[j,k];
(4)重復(2)(3)共n-1次。
代碼：proc short_dij;
begin
for i:=1 to n do
begin
dist[i]:=cost[v0,i];
if dist[i]<max then path[i]:=v0 else path[i]:=-1; end;
flag[I]:=true;
for k:=1 to n-1 do
begin
wm:=max; j:=v0;
for i:=1 to n do
if not(flag[i]) and (dist[i]<wm) then begin j:=i; m:=dist[i]; end;
flag[j]:=true; for i:=1 to n do if not(flag[i]) and (dist[j]+cost[j,i]<dist[i]) then
begin dist[i]:=dist[j]+cost[j,i]; path[i]:=j; end;
end;
end; 其中：cost：鄰接矩陣；
path[i]：存儲從v0到頂點i的最短路徑；是以集合作為數組元素；
dist[i]：存儲相應路徑長度；
flag[i]：表示已處理的頂點。
練習5：Dijkstra演算法練習
【問題描述】從文件中讀入帶權圖的信息，按Dijkstra演算法根據給定源點求出從源點法到該圖中其餘頂點的最短路徑。
【輸入文件】第一行：一個整數L：L=0表示無向圖，L=1表示有向圖；第二行三個整數m、n和k，分別表示圖的結點數、圖中的邊數以及源點。以下n行表示n條邊：每一行三個數x、y和z，z表示x與y之間邊的權值。
【輸出文件】共m-1行，每一行的數據包括：頂點： 最短路徑：路徑，如果不存在路徑，數據為：頂點：No path。
【示例】輸入：1 輸出：2：No path
6 8 1 3：10：1 3
1 3 10 4：50：1 5 4
1 5 30 5：30：1 5
1 6 100 6：60：1 5 4 6
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
練習6：路由選擇問題
【問題描述】
X城有一個含有N個節點的通信網路，在通信中，我們往往關心信息從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。
任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。
任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。
【輸入文件】
第1行： N I J (節點個數 起始節點 目標節點)
第2—N+1行： Sk1 Sk2…SkN (節點K到節點J的距離為SkJ K=1，2，……，N)
最後一行： P T1 T2……Tp (故障節點的個數及編號)
【輸出文件】
S0 S1 S2 (S1<=S2 從節點I到節點J至少有兩條不同路徑)
【輸入輸出樣例】
route.in
5 1 5
0 10 5 0 0
10 0 0 6 20
5 0 0 30 35
0 6 30 0 6
0 20 35 6 0
1 2
route.out
40 22 30

2、每對頂點之間的最短路徑
求圖中每對頂點之間的最短路徑是指把圖中任意兩個頂點vi和vj（i≠j）之間的最短路徑都計算出來。解決此問題有兩種方法：一是分別以圖中的每個頂點為源點共調用n次迪傑斯特拉演算法，此方法的時間復雜性為O（n3）；二是採用下面介紹的弗洛伊德（Floyed）演算法，此演算法的時間復雜性仍為O（n3），但比較簡單。 弗洛伊德演算法實際上是一個動態規劃的演算法。從圖的鄰接矩陣開始，按照頂點v1，v2，…，vn的次序，分別以每個頂點vk（1≤k≤n）作為新考慮的中間點，在第k-1次運算Ak-1 （A（0）為原圖的鄰接矩陣G） 的基礎上，求出每對頂點vi到vj的最短路徑長度計算公式為：

Floyd演算法：
proc shortpath_floyd;
begin
for i:=1 to n do for j:=1 to n do
begin
length[i,j]:=cost[i,j];
if length[i,j]<max then path[i,j]:=[i]+[j];
end;
for k:=1 to n do for i:=1 to n do for j:=1 to n do
if length[i,k]+length[k,j]<length[i,j] then
begin
length[i,j]:=length[i,k]+length[k,j];
path[i,j]:=path[i,k]+path[k,j];
end;
end;
其中：cost為鄰接矩陣；
path[i,j]：表示頂點i到j的最短路徑；
length[i,j]：
練習7：Floyd演算法練習
【問題描述】從文件中讀入帶權圖的信息，按Dijkstra演算法根據給定源點求出從源點到該圖中其餘頂點的最短路徑。
【輸入文件】第一行：一個整數L：L=0表示無向圖，L=1表示有向圖；第二行三個整數m、n，分別表示圖的結點數和圖中的邊數。以下n行表示n條邊：每一行三個數x、y和z，z表示x與y之間邊的權值。第n+2行：整數R，以下R行每行一個整數表示頂點標號作為源點。
【輸出文件】共R行，每一行的數據表示源點到其餘頂點的距離，按頂點編號由小大輸出，如果沒有路徑，輸出-1。
【示例】輸入：1 輸出：-1 10 50 30 60
6 8 -1 –1 –1 20 30
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
2
1
5

5. 最短路徑的Dijkstra演算法

Dijkstra演算法（迪傑斯特拉）是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。可以用堆優化。
Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。
其採用的是貪心法的演算法策略
大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復第2和第3步,直到OPEN表為空，或找到目標點。 #include<iostream>#include<vector>usingnamespacestd;voiddijkstra(constint&beg,//出發點constvector<vector<int>>&adjmap,//鄰接矩陣，通過傳引用避免拷貝vector<int>&dist,//出發點到各點的最短路徑長度vector<int>&path)//路徑上到達該點的前一個點//負邊被認作不聯通//福利：這個函數沒有用任何全局量，可以直接復制！{constint&NODE=adjmap.size();//用鄰接矩陣的大小傳遞頂點個數，減少參數傳遞dist.assign(NODE,-1);//初始化距離為未知path.assign(NODE,-1);//初始化路徑為未知vector<bool>flag(NODE,0);//標志數組，判斷是否處理過dist[beg]=0;//出發點到自身路徑長度為0while(1){intv=-1;//初始化為未知for(inti=0;i!=NODE;++i)if(!flag[i]&&dist[i]>=0)//尋找未被處理過且if(v<0||dist[i]<dist[v])//距離最小的點v=i;if(v<0)return;//所有聯通的點都被處理過flag[v]=1;//標記for(inti=0;i!=NODE;++i)if(adjmap[v][i]>=0)//有聯通路徑且if(dist[i]<0||dist[v]+adjmap[v][i]<dist[i])//不滿足三角不等式{dist[i]=dist[v]+adjmap[v][i];//更新path[i]=v;//記錄路徑}}}intmain(){intn_num,e_num,beg;//含義見下cout<<輸入點數、邊數、出發點：;cin>>n_num>>e_num>>beg;vector<vector<int>>adjmap(n_num,vector<int>(n_num,-1));//默認初始化鄰接矩陣for(inti=0,p,q;i!=e_num;++i){cout<<輸入第<<i+1<<條邊的起點、終點、長度（負值代表不聯通）：;cin>>p>>q;cin>>adjmap[p][q];}vector<int>dist,path;//用於接收最短路徑長度及路徑各點dijkstra(beg,adjmap,dist,path);for(inti=0;i!=n_num;++i){cout<<beg<<到<<i<<的最短距離為<<dist[i]<<，反向列印路徑：;for(intw=i;path[w]>=0;w=path[w])cout<<w<<<-;cout<<beg<<' ';}}

6. 短鏈接系統的演算法原理

平時我們在上網的時候，印象最深刻的有一次是短鏈接的服務。例如：平時在微信上看一個網頁的時候，如果我們選擇在瀏覽器打開的時候，會看到很長的URL，我們分享的時候，會看到一個很短URL，這就是本次所說的短鏈接的應用之一。
長鏈接示例： https://mp.weixin.qq.com/s?__biz=MzAxNzMwOTQ0NA==&mid=2653355437&idx=1&sn=&chksm=31c947&scene=0&key=01a8800b6fd6b36be097&ascene=0&uin=ODU5NDQ1NjI1&devicetype=iMac+MacBookAir6%2C2+OSX+OSX+10.12.6+build(16G29)&version=12020810&nettype=WIFI&fontScale=100&pass_ticket=IvPqxUmCJqZg9%
我用短鏈接系統生成的（長期會失效）： https://0x9.me/FAKcm

廢話少說，短鏈接就是我們很短的鏈接。我們的目的是要把長鏈接轉換成短鏈接。接下來我要提出一個問題：怎麼把長鏈接轉換成短鏈接呢？
1.壓縮
實現一種演算法，將長地址轉換成短地址。然後再實現一種逆運算，將短地址轉換成原來的地址。其實仔細的想一下，這是不可能的。
2.Hash演算法
可能是大多數人都會想到的一種方法。有人會提出，將一個長URL進行Hash運算，然後將Hash值作為這個長鏈接的唯一標示。但是通常容易想到的不一定是最優的，我們知道Hash有可能產生碰撞，Hash碰撞的解決，會增強短鏈接系統的復雜度。

顧名思義這個系統的第一個請求過來了，我們以微博為例，短鏈接系統的第一個請求我們可以給變為t.cn/0，第二個t.cn/1等等；
實現的方式也會很簡單
1、小型的系統用MySQL的自增索引就可以滿足。
2、大型系統可以考慮分布式key-value系統。

發號策略是這樣的，當一個新的鏈接過來時，發號器發一個號與之對應。往後只要有新鏈接過來，發號器不停發號就好。舉個例子，第一個進來的鏈接發號器發0號，對應的短鏈接為 xx.xxx/0，第二個進來的鏈接發號器發1號，對應的短鏈接為 xx.xxx/1，以此類推。
發號器發出的10進制號需要轉換成62進制，這樣可以大大縮短號碼轉換成字元串後的長度。比如發號器發出 10,000,000,000 這個號碼，如果不轉換成62進制，直接拼接在域名後面，得到這樣一個鏈接 xx.xxx/10000000000。將上面的號碼轉換成62進制，結果為AOYKUa，長度只有6位，拼接得到的鏈接為 xx.xxx/AOYKUa。可以看得出，進制轉換後得到的短鏈接長度變短了一些。6位62進制數，對應的號碼空間為626，約等於568億，所以基本上不用擔心發號器無號可發的情況。

上面設計看起來有一個單點，那就是發號器。如果做成分布式的，那麼多節點要保持同步加1，多點同時寫入。這樣難以避免產生單點性能瓶頸。因此我們可以考慮將單點變為多點。我們可以引入多個機器，我們可以設定機器A發號只發向100取余等於0的數字100n，同理機器B只發向100取余等於1數字 100n+1，以此類推，各個機器相互獨立互不幹擾，我們可以隨時擴展我們的機器了。

同一長鏈接，每次轉成的短鏈接不一定一樣，原因在於如果查詢緩存時，如果未命中，發號器會發新號給這個鏈接。需要說明的是，緩存應該緩存經常轉換的熱門鏈接，假設設定緩存過期時間為一小時，如果某個鏈接很活躍的話，緩存查詢命中後，緩存會刷新這個鏈接的存活時間，重新計時，這個鏈接就會長久存在緩存中。
我們也可以引入LRU演算法。進行淘汰我們不經常使用到的鏈接。

選取301，還是302？
301是永久重定向，302是臨時重定向。

如果選擇301 ：短地址生成以後就不會變化，所以用301是符合http語義的。同時對伺服器壓力也會有一定減少。這樣一來，我們就無法統計到短地址被點擊的次數了。
如果選擇302 ：選擇302雖然會增加伺服器壓力，但是可以統計到短地址被點擊的次數了，我可以針對點擊的次數來進行後期的大數據處理，機器學習，以及推薦演算法。
選擇302還是301，想必讀者心中有肯定有數了。

7. 經典樹與圖論（最小生成樹、哈夫曼樹、最短路徑問題---Dijkstra演算法）

最小生成樹：在連通網的所有生成樹中，所有邊的代價和最小的生成樹，稱為最小生成樹。

1.Kruskal演算法
此演算法可以稱為「加邊法」，初始最小生成樹邊數為0，每迭代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合里。

Prim演算法
此演算法可以稱為「加點法」，每次迭代選擇代價最小的邊對應的點，加入到最小生成樹中。演算法從某一個頂點s開始，逐漸長大覆蓋整個連通網的所有頂點。

1.圖的所有頂點集合為VV；初始令集合u={s},v=V−uu={s},v=V−u;
2.在兩個集合u,vu,v能夠組成的邊中，選擇一條代價最小的邊(u0,v0)(u0,v0)，加入到最小生成樹中，並把v0v0並入到集合u中。
3.重復上述步驟，直到最小生成樹有n-1條邊或者n個頂點為止。

哈夫曼樹又稱最優二叉樹。它是 n 個帶權葉子結點構成的所有二叉樹中，帶權路徑長度 WPL 最小的二叉樹。

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

注意：為了使得到的哈夫曼樹的結構盡量唯一，通常規定生成的哈夫曼樹中每個結點的左子樹根結點的權小於等於右子樹根結點的權。

在電報通信中，電文是以二進制的0、1序列傳送的，每個字元對應一個二進制編碼，為了縮短電文的總長度，採用不等長編碼方式，構造哈夫曼樹，
將每個字元的出現頻率作為字元結點的權值賦予葉子結點，每個分支結點的左右分支分別用0和1編碼，從樹根結點到每個葉子結點的路徑上
所經分支的0、1編碼序列等於該葉子結點的二進制編碼。如上文所示的哈夫曼編碼如下：

最短路徑問題介紹
問題解釋：
從圖中的某個頂點出發到達另外一個頂點的所經過的邊的權重和最小的一條路徑，稱為最短路徑。

初始狀態：S是已計算出最短路徑的頂點集合，U是未計算除最短路徑的頂點的集合！
第1步：將頂點D加入到S中。
此時，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 注:C(3)表示C到起點D的距離是3。

第2步：將頂點C加入到S中。
上一步操作之後，U中頂點C到起點D的距離最短；因此，將C加入到S中，同時更新U中頂點的距離。以頂點F為例，之前F到D的距離為∞；但是將C加入到S之後，F到D的距離為9=(F,C)+(C,D)。
此時，S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}。

第3步：將頂點E加入到S中。
上一步操作之後，U中頂點E到起點D的距離最短；因此，將E加入到S中，同時更新U中頂點的距離。還是以頂點F為例，之前F到D的距離為9；但是將E加入到S之後，F到D的距離為6=(F,E)+(E,D)。
此時，S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}。

第4步：將頂點F加入到S中。
此時，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。

第5步：將頂點G加入到S中。
此時，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。

第6步：將頂點B加入到S中。
此時，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。

第7步：將頂點A加入到S中。
此時，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

此時，起點D到各個頂點的最短距離就計算出來了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。