Trouver les chemins les plus courts

Laluan terpendek antara dua bucu ialah laluan dengan jumlah berat minimum.
Memandangkan graf dengan pemberat bukan negatif di tepi, algoritma terkenal untuk mencari laluan terpendek antara dua bucu ditemui oleh Edsger Dijkstra, seorang saintis komputer Belanda. Untuk mencari laluan terpendek dari bucu s ke bucu v, algoritma Dijkstra mencari laluan terpendek dari s ke semua bucu. Jadi algoritma Dijkstra dikenali sebagai sumber tunggal algoritma laluan terpendek. Algoritma menggunakan kos[v] untuk menyimpan kos laluan terpendek dari bucu v ke bucu sumber s. kos[s] ialah 0. Pada mulanya tetapkan infiniti kepada kos[v] untuk semua bucu lain. Algoritma berulang kali mencari bucu u dalam V – T dengan kos[u] terkecil dan bergerak u ke T .

Algoritma diterangkan dalam kod di bawah.

Input: a graph G = (V, E) with non-negative weights
Output: a shortest path tree with the source vertex s as the root
 1 ShortestPathTree getShortestPath(s) {
 2 Let T be a set that contains the vertices whose
 3 paths to s are known; Initially T is empty;
 4 Set cost[s] = 0; and cost[v] = infinity for all other vertices in V;
 5
 6 while (size of T < n) {
 7 Find u not in T with the smallest cost[u];
 8 Add u to T;
 9 for (each v not in T and (u, v) in E)
10 if (cost[v] > cost[u] + w(u, v)) {
11 cost[v] = cost[u] + w(u, v); parent[v] = u;
12 }
13 }
14 }

Algoritma ini sangat serupa dengan Prim untuk mencari pokok rentang minimum. Kedua-dua algoritma membahagikan bucu kepada dua set: T dan V - T. Dalam kes algoritma Prim, set T mengandungi bucu yang telah ditambahkan pada pokok. Dalam kes Dijkstra, set T mengandungi bucu yang laluan terpendeknya ke sumber telah ditemui. Kedua-dua algoritma berulang kali mencari bucu daripada V – T dan menambahnya pada T. Dalam kes algoritma Prim, bucu adalah bersebelahan dengan beberapa bucu dalam set dengan berat minimum di tepi. Dalam algoritma Dijkstra, bucu bersebelahan dengan beberapa bucu dalam set dengan jumlah kos minimum kepada sumber.

Algoritma bermula dengan menetapkan kos[s] kepada 0 (baris 4), menetapkan kos[v] kepada infiniti untuk semua bucu lain. Ia kemudian menambah bucu secara berterusan (katakan u) daripada V – T ke T dengan terkecil kos[u] (baris 7– 8), seperti yang ditunjukkan dalam Rajah di bawah a. Selepas menambah u pada T, algoritma mengemas kini kos[v] dan ibu bapa[v] untuk setiap v bukan dalam T jika (u, v) berada dalam T dan kos[v] > kos[u] + w(u, v) (baris 10–11).

Mari kita menggambarkan algoritma Dijkstra menggunakan graf dalam Rajah di bawah a. Katakan puncak sumber ialah 1. Oleh itu, kos[1] = 0 dan kos untuk semua bucu lain pada mulanya ialah ∞, seperti ditunjukkan dalam Rajah di bawah b. Kami menggunakan ibu bapa[i] untuk menandakan ibu bapa i dalam laluan. Untuk kemudahan, tetapkan induk nod sumber kepada -1.

Pada mulanya ditetapkan T adalah kosong. Algoritma memilih puncak dengan kos terkecil. Dalam kes ini, bucu ialah 1. Algoritma menambah 1 kepada T, seperti yang ditunjukkan dalam Rajah di bawah a. Selepas itu, ia melaraskan kos untuk setiap bucu bersebelahan dengan 1. Kos untuk bucu 2, 0, 6 dan 3 dan ibu bapa mereka kini dikemas kini, seperti yang ditunjukkan, seperti ditunjukkan dalam Rajah di bawah b.

Bucu 2, 0, 6 dan 3 bersebelahan dengan bucu sumber dan bucu 2 ialah yang dalam V-T dengan kos terkecil, jadi tambah 2 kepada T, seperti yang ditunjukkan dalam Rajah di bawah dan kemas kini kos dan induk untuk bucu dalam V-T dan bersebelahan dengan 2. kos[0] kini dikemas kini kepada 6 dan induknya ditetapkan kepada 2. Garis anak panah dari 1 hingga 2 menunjukkan bahawa 1 ialah induk kepada 2 selepas 2 ditambah ke dalam T.

Maintenant T contient {1, 2}. Le sommet 0 est celui de V-T avec le plus petit coût, alors ajoutez 0 à T, comme indiqué dans la figure ci-dessous et mettez à jour le coût et parent pour les sommets en V-T et adjacents à 0 le cas échéant. cost[5] est maintenant mis à jour à 10 et son parent est défini sur 0 et cost[6] est maintenant mis à jour sur 8 et son parent est défini sur 0.

Maintenant T contient {1, 2, 0}. Le sommet 6 est celui de V-T avec le plus petit coût, alors ajoutez 6 à T, comme indiqué dans la figure ci-dessous et mettez à jour le coût et parent pour les sommets en V-T et adjacents à 6 le cas échéant.

Maintenant T contient {1, 2, 0, 6}. Le sommet 3 ou 5 est celui en V-T avec le plus petit coût. Vous pouvez ajouter 3 ou 5 dans T. Ajoutons 3 à T, comme le montre la figure ci-dessous et mettons à jour le coût et le parent pour les sommets dans V-T et adjacents à 3 le cas échéant. cost[4] est maintenant mis à jour à 18 et son parent est défini sur 3.

Maintenant T contient {1, 2, 0, 6, 3}. Le sommet 5 est celui de V-T avec le plus petit coût, alors ajoutez 5 à T, comme indiqué dans la figure ci-dessous et mettez à jour le coût et parent pour les sommets en V-T et adjacents à 5 le cas échéant. cost[4] est maintenant mis à jour à 10 et son parent est défini sur 5.

Maintenant T contient {1, 2, 0, 6, 3, 5}. Le sommet 4 est celui de V-T avec le plus petit coût, alors ajoutez 4 à T, comme indiqué dans la figure ci-dessous.

Comme vous pouvez le voir, l'algorithme trouve essentiellement tous les chemins les plus courts à partir d'un sommet source, ce qui produit un arbre enraciné au sommet source. Nous appelons cet arbre un arbre à source unique à chemin le plus court (ou simplement un arbre à chemin le plus court). Pour modéliser cet arbre, définissez une classe nommée ShortestPathTree qui étend la classe Tree, comme le montre la figure ci-dessous. ShortestPathTree est défini comme une classe interne dans WeightedGraph aux lignes 200 à 224 de WeightedGraph.java.

La méthode getShortestPath(int sourceVertex) a été implémentée aux lignes 156 à 197 dans WeightedGraph.java. La méthode définit cost[sourceVertex] sur 0 (ligne 162) et cost[v] sur l'infini pour tous les autres sommets (lignes 159-161). Le parent de sourceVertex est défini sur -1 (ligne 166). T est une liste qui stocke les sommets ajoutés dans l'arbre du chemin le plus court (ligne 169). Nous utilisons une liste pour T plutôt qu'un ensemble afin d'enregistrer l'ordre des sommets ajoutés à T.

Initialement, T est vide. Pour développer T, la méthode effectue les opérations suivantes :

1. Find the vertex u with the smallest cost[u] (lines 175–181) and add it into T (line 183).
2. After adding u in T, update cost[v] and parent[v] for each v adjacent to u in V-T if cost[v] > cost[u] + w(u, v) (lines 186–192).

Once all vertices from s are added to T, an instance of ShortestPathTree is created (line 196).

The ShortestPathTree class extends the Tree class (line 200). To create an instance of ShortestPathTree, pass sourceVertex, parent, T, and cost (lines 204–205). sourceVertex becomes the root in the tree. The data fields root, parent, and searchOrder are defined in the Tree class, which is an inner class defined in AbstractGraph.

Note that testing whether a vertex i is in T by invoking T.contains(i) takes O(n) time, since T is a list. Therefore, the overall time complexity for this implemention is O(n^3).

Dijkstra’s algorithm is a combination of a greedy algorithm and dynamic programming. It is a greedy algorithm in the sense that it always adds a new vertex that has the shortest distance to the source. It stores the shortest distance of each known vertex to the source and uses it later to avoid redundant computing, so Dijkstra’s algorithm also uses dynamic programming.

The code below gives a test program that displays the shortest paths from Chicago to all other cities in Figure below and the shortest paths from vertex 3 to all vertices for the graph in Figure below a, respectively.

package demo;

public class TestShortestPath {

    public static void main(String[] args) {
String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
                {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
                {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
                {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
                {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
                {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
                {6, 5, 983}, {6, 7, 214},
                {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
                {8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
                {9, 8, 661}, {9, 11, 1187},
                {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
                {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
        };

        WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
        WeightedGraph<String>.ShortestPathTree tree1 = graph1.getShortestPath(graph1.getIndex("Chicago"));
        tree1.printAllPaths();

        // Display shortest paths from Houston to Chicago       
        System.out.println("Shortest path from Houston to Chicago: ");
        java.util.List<String> path = tree1.getPath(graph1.getIndex("Houston"));
        for(String s: path) {
            System.out.print(s + " ");
        }

        edges = new int[][]{
            {0, 1, 2}, {0, 3, 8},
            {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
            {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
            {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
            {4, 2, 5}, {4, 3, 6}
        };

        WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
        WeightedGraph<Integer>.ShortestPathTree tree2 = graph2.getShortestPath(3);
        System.out.println("\n");
        tree2.printAllPaths();
    }

}

All shortest paths from Chicago are:
A path from Chicago to Seattle: Chicago Seattle (cost: 2097.0)
A path from Chicago to San Francisco:
Chicago Denver San Francisco (cost: 2270.0)
A path from Chicago to Los Angeles:
Chicago Denver Los Angeles (cost: 2018.0)
A path from Chicago to Denver: Chicago Denver (cost: 1003.0)
A path from Chicago to Kansas City: Chicago Kansas City (cost: 533.0)
A path from Chicago to Chicago: Chicago (cost: 0.0)
A path from Chicago to Boston: Chicago Boston (cost: 983.0)
A path from Chicago to New York: Chicago New York (cost: 787.0)
A path from Chicago to Atlanta:
Chicago Kansas City Atlanta (cost: 1397.0)
A path from Chicago to Miami:
Chicago Kansas City Atlanta Miami (cost: 2058.0)
A path from Chicago to Dallas: Chicago Kansas City Dallas (cost: 1029.0)
A path from Chicago to Houston:
Chicago Kansas City Dallas Houston (cost: 1268.0)
Shortest path from Houston to Chicago:
Houston Dallas Kansas City Chicago

All shortest paths from 3 are:
A path from 3 to 0: 3 1 0 (cost: 5.0)
A path from 3 to 1: 3 1 (cost: 3.0)
A path from 3 to 2: 3 2 (cost: 4.0)
A path from 3 to 3: 3 (cost: 0.0)
A path from 3 to 4: 3 4 (cost: 6.0)

The program creates a weighted graph for Figure above in line 27. It then invokes the getShortestPath(graph1.getIndex("Chicago")) method to return a Path object that contains all shortest paths from Chicago. Invoking printAllPaths() on the ShortestPathTree object displays all the paths (line 30).

The graphical illustration of all shortest paths from Chicago is shown in Figure below. The shortest paths from Chicago to the cities are found in this order: Kansas City, New York, Boston, Denver, Dallas, Houston, Atlanta, Los Angeles, Miami, Seattle, and San Francisco.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!