最優路徑演算法
『壹』 最佳路線演算法
如果節點數n比較小的話，狀態壓縮一下就可以了。
就是說dist[i][j]表示到達第i個點的時候，已經走過的節點的狀態為j的最短距離，然後再用dijkstra或者spfa跑一邊求出 dist[1][(1 << n) - 1]即使答案。
『貳』 路徑分析的最優路徑分析方法
1．道路預處理
進行道路數據錄入時，往往在道路的交叉接合處出現重疊或相離的情況，不宜計算機處理。因此，需要對原始數據進行預處理，使道路接合符合處理要求。進行預處理時，取每條線段的首末節點坐標為圓心，以給定的閾值為半徑作圓域，判斷其他線段是否與圓域相交，如果相交，則相交的各個線對象共用一個節點號。
2．道路自動斷鏈
對道路進行預處理之後即可獲得比較理想的數據，在此基礎上再進行道路的自動斷鏈。步驟如下：
（1）取出所有線段記錄數n，從第一條線段開始；
（2）找出所有與之相交的線段並求出交點數m；
（3）將m個交點和該線段節點在判斷無重合後進行排序；
（4）根據交點數量，該線段被分成m+1段；
（5）第一段在原始位置不變，後m段從記錄尾開始遞增；
（6）重復（2）～（5），循環至n。
3．節點匹配
拓撲關系需使用統一的節點。節點匹配方法是按記錄順序將所有線段的始末點加上相應節點號，坐標相同的節點共用一個節點號，與前面所有線段首末點都不相同的節點按自然順序遞增1。
4．迪傑克斯特拉（Dijkstra）演算法
經典的圖論與計算機演算法的有效結合，使得新的最短路徑演算法不斷涌現。目前提出的最短路徑演算法中，使用最多、計算速度比較快，又比較適合於計算兩點之間的最短路徑問題的數學模型就是經典的Dijkstra演算法。
該演算法是典型的單源最短路徑演算法，由Dijkstra EW於1959年提出，適用於所有弧的權均為非負的情況，主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。該演算法的基本思想是：認為兩節點間最佳路徑要麼是直接相連，要麼是通過其他已找到的與起始點的最佳路徑的節點中轉點。定出起始點P0後，定能找出一個與之直接相連且路徑長度最短的節點，設為P1，P0到P1就是它們間的最佳路徑。
Dijkstra演算法的基本流程如下：首先將網路中所有節點分成兩組，一組包含了已經確定屬於最短路徑中點的集合，記為S（該集合在初始狀態只有一個源節點，以後每求得一條最短路徑，就將其加入到集合S中，直到全部頂點都加入到S中，演算法就結束了）；另一組是尚未確定最短路徑的節點的集合，記為V，按照最短路徑長度遞增的次序依次把第二組的頂點加入到第一組中，在加入的過程中總保持從源點到S中各頂點的最短路徑長度不大於從源點到V中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點距離就是從源點到此頂點的最短路徑長度，V中的頂點距離是從源點到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
『叄』 導航系統最優路徑選擇的演算法
請學習 最短路徑演算法。
『肆』 求解：圖論中常見的最短路徑演算法有幾種都是什麼
主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、
『伍』 計算機網路的最短路徑演算法有哪些對應哪些協議
用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，本文主要介紹其中的三種。
最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：
確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。
確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。
全局最短路徑問題：求圖中所有的最短路徑。
Floyd
求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度O(V^3)。
Floyd-Warshall演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題。
Floyd-Warshall演算法的時間復雜度為O(N^3)，空間復雜度為O(N^2)。
Floyd-Warshall的原理是動態規劃：
設Di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。
若最短路徑經過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；
若最短路徑不經過點k，則Di,j,k = Di,j,k-1。
因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。
在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。
Floyd-Warshall演算法的描述如下：
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (Di,k + Dk,j < Di,j) then
Di,j ← Di,k + Dk,j;
其中Di,j表示由點i到點j的代價，當Di,j為 ∞ 表示兩點之間沒有任何連接。
Dijkstra
求單源、無負權的最短路。時效性較好，時間復雜度為O（V*V+E）,可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。
當是稀疏圖的情況時，此時E=V*V/lgV，所以演算法的時間復雜度可為O（V^2） 。可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
Bellman-Ford
求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路），時效性較好，時間復雜度O（VE）。
Bellman-Ford演算法是求解單源最短路徑問題的一種演算法。
單源點的最短路徑問題是指：給定一個加權有向圖G和源點s，對於圖G中的任意一點v，求從s到v的最短路徑。
與Dijkstra演算法不同的是，在Bellman-Ford演算法中，邊的權值可以為負數。設想從我們可以從圖中找到一個環
路（即從v出發，經過若干個點之後又回到v）且這個環路中所有邊的權值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。 而Bellman-Ford演算法具有分辨這種負環路的能力。
SPFA
是Bellman-Ford的隊列優化，時效性相對好，時間復雜度O（kE）。（k< 與Bellman-ford演算法類似，SPFA演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。所不同的是，SPFA演算法通過維護一個隊列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重復的操作次數。
SPFA演算法可以用於存在負數邊權的圖，這與dijkstra演算法是不同的。
與Dijkstra演算法與Bellman-ford演算法都不同，SPFA的演算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。
在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度僅為O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時演算法退化為Bellman-ford演算法，其時間復雜度為O(VE)。
SPFA演算法在負邊權圖上可以完全取代Bellman-ford演算法，另外在稀疏圖中也表現良好。但是在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra演算法，以及它的使用堆優化的版本。通常的SPFA。
『陸』 路徑規劃。求解題思路！！！通過給出點和路徑，計算最優路徑。如何避免環路
public class Edge { private String startNode; private String endNode; public String getStartNode() { return startNode; } public void setStartNode(String startNode) { this.startNode = startNode; } public String getEndNode() { return endNode; } public void setEndNode(String endNode) {
this.endNode = endNode; } }
public class Node { private String name; private Integer weight; private List<Edge> edges = new ArrayList<Edge>(); public String getName() { return name; } public void setName(String name) { this.name = name; } public Integer getWeight() { return weight; } public void setWeight(Integer weight) { this.weight = weight; } public List<Edge> getEdges() { return edges; } public void addEdges(String endNode) { Edge edge = new Edge(); edge.setStartNode(this.getName()); edge.setEndNode(endNode); this.edges.add(edge); } }
public class Graph { private Map<String,Node> nodeMap = new HashMap<String, Node>();
public Map<String, Node> getNodeMap() { return nodeMap; } public void addNode(Node node){ if(node==null){ throw new RuntimeException("bad Node"); } this.nodeMap.put(node.getName(),node); } public void addEdge(String startNodeName,String endNodeName){ if(nodeMap==null) { throw new RuntimeException("nodeMap is null"); } if(nodeMap.get(startNodeName)==null){ throw new RuntimeException("startNode is null"); } if(nodeMap.get(endNodeName)==null){ throw new RuntimeException("endNode is null"); } nodeMap.get(startNodeName).addEdges(endNodeName); } /** * 此方法返回fromNode到toNode的最短路徑，但是如果有環路則會陷入死循環 * @param fromNodeName * @param toNodeName * @return */ public int getMostPath(String fromNodeName,String toNodeName){ Node fromNode = nodeMap.get(fromNodeName); List<Edge> edges = fromNode.getEdges(); if(edges==null){ return -1; } int path = 0; for (Edge edge :edges){
int tempPath = fromNode.getWeight(); String endNodeName = edge.getEndNode(); if(!endNodeName.equals(toNodeName)){ int mostPath = getMostPath(endNodeName, toNodeName); if(mostPath==-1){ continue; } tempPath+=mostPath; }else { tempPath+=nodeMap.get(endNodeName).getWeight(); } if(path<tempPath){ path=tempPath; } } return path; } /** * 可跳過閉環並且返迴路徑list的方法 * @param fromNodeName * @param toNodeName * @param pathList * @return */ public int getMostPathResult(String fromNodeName,String toNodeName,LinkedHashSet<String> pathList){ if(fromNodeName.equals(toNodeName)){ System.out.println("ERR : fromNode == toNode"); return -1; } Node fromNode = nodeMap.get(fromNodeName); List<Edge> edges = fromNode.getEdges(); if(edges==null){ return -1; } boolean add = pathList.add(fromNodeName); if(!add){ System.out.println("有閉環！"+"node:"+fromNodeName+"，path:"+pathList); return -1; }
int path = 0; LinkedHashSet<String> temp = new LinkedHashSet<String>(); temp.addAll(pathList); for (Edge edge :edges){ LinkedHashSet<String> temp2 = new LinkedHashSet<String>(); temp2.addAll(temp); int tempPath = fromNode.getWeight(); String endNodeName = edge.getEndNode(); if(!endNodeName.equals(toNodeName)){ int mostPath = getMostPathResult(endNodeName, toNodeName,temp2); if(mostPath==-1){ continue; } tempPath+=mostPath; }else { tempPath+=nodeMap.get(endNodeName).getWeight(); temp2.add(toNodeName); } if(path<tempPath){ path=tempPath; pathList.clear(); pathList.addAll(temp2); } } return path; } }
『柒』 圖論中常見的最短路徑演算法有幾種都是什麼
主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、
『捌』 求一個最優路徑演算法的思路
同意樓上，最長路徑是NPC問題，不存在多項式演算法。
證明是簡單的：
1、最長無環路問題的判定版本是「給定有向圖D和整數k，問D中是否存在長度大於或等於k的無環路」（這一表述對有權圖和無權圖都有效）。
2、將Hamilton路問題規約到最長無環路問題（的判定版本）是顯然的：輸入一個n頂點的有向圖D，直接問：有向圖D中是否存在長度大於等於n-1的無環路？
簡言之，對任意n頂點的有向圖D，假如能夠D中的找到最長無環路P，那麼就能立即知道D中是否存在Hamilton路（只需看P的長度是否為n-1即可），從而最長無環路問題是NPC。
小規模就直接DFS吧。大規模的時候DFS剪枝。不過確實不好做呀。
有向無圈圖的話可以用dijstra貪心，或者簡單用folyed演算法就可以了（把最小化變為最大化）。
有圈的話您……或者能縮圈么？可以考慮。總之比較復雜。
『玖』 最優路徑問題
演算法肯定有，就怕做出來木有採納之類的，你要什麼演算法，java或者C++之類的？
『拾』 "最短路徑優先演算法"的優缺點
這個演算法一般出現在網路中，用於路由器的路由定址，我也只了解這方面的優缺點。如果不對，LZ就別看了。
所謂最短路徑，實際上說的是跳數。比如從一條路走會經過三個路由器，而從另一條路走，會經過兩個路由器，那麼此演算法會判斷2跳比3跳要短，但具體每一跳會花多長時間，經過多長路程，它不會考慮的。所以不一定演算法的最短路徑就是真實的最短。因為很多因素演算法沒有考慮，比如通信質量，網線長度……
C語言我只看過一個模擬現實的例子，大概是說公車走什麼路線長度最短，那個演算法考慮的是路線的長短，而不是跳數，優點當然就是路線的絕對最短，缺點就是沒考慮到其他現實因素，比如是否堵車（相當於網路通信質量）之類。
總之不管什麼演算法，考慮到的因素就是它的優點，反過來說，缺點往往就是演算法忽略的因素。
補充一下，如果說的不是演算法本身的優劣，而是細節的實現方面，那就是從時間復雜度和空間復雜度兩個方面去考慮了，希望對LZ有用。