[Algorithm] Find the shortest path Dijkstra, Floyd

December 29, 2014 nguyenvanquan7826 TT Graphs 139 responses


Update 25/05/2014: Do some of your comments, so I wrote more 1 Dijkstra's algorithm program structure and function by the way also slightly revised code for brighter and more accurate ^^.

Update 27/09/2014: additional pascal code of the algorithm here: http://ideone.com/c7J0dq

Content
Dijkstra Algorithm
Floyd algorithm
Advanced Code for 2 algorithm

Update 14/06/2014: The simulation algorithm Dijkstra

In this article only refers to the algorithm to find the shortest path Dijkstra and Floyd, some related terms I will not explain or define, you find out in the book or on the Internet.

The problem of single-source shortest path problem is to find a path between two vertices such that the sum of the weights of the edges that make up the smallest way. Or to put it mathematically is:
For single connected graph, weighted G =(The,And). Find the distance d(the,b) from a given vertex to a vertex of G and b any finding the shortest path from a to b.

As the post title, we will learn 2 algorithm to solve using graph adjacency matrix structure(note we consider the weight of the graph is not negative).

Adjacency matrix of a graph with n vertices is a square matrix G n is the number of rows of columns. G[in][j] the length of the path from i to vertex j top. Considering the undirected graph G[in][j] G =[j][in]. Length from top to itself is 0 (G[in][in] = 0). If between 2 i and j edges of the graph does not exist the way it G[in][j] = Infinity (∞). However, the performance of the computer, the value is set to ∞ 1 constant is very large or the total value of the matrix (total length of the edge).

1. Dijkstra Algorithm

About Dijkstra algorithm has 2 type is to find the shortest path from 1 sources to top 1 top destination and find the shortest path from 1 source vertex to the top left of the graph, and here I will talk about stuff 1. (the second kind you can find on the net or just change the line while (with[b] == 0) (current 43 by code 1 & current 76 by code 2) from the loop browser 0 n-1 is going to find all the vertices).

– Use 1 Mangal only[] – Only[in] is the shortest distance from a vertex to vertex i.

– Use 1 Plate S marking the special vertex i (the peak current i that time, the path from a to i is the shortest).

– Using array P[] marked paths. P[j] If i = i j is the peak ahead of the shortest path.

– Reset extremely valuable for top pair no way.

– Initialize all the way from Asia to the other peaks in extremely.

– Initialize path from a primary to a = 0.

– Browse all the vertices of the graph V

+ Find top i not in S that the path from a to i is the shortest for inclusion in S. If you can not find any means approved top of the peak can go and still have not found the top destination => could not walk.

+ If you find the vertex i j browse all vertices not in S. New only[in] + G[in][j] < Only[j] (where G[in][j] is the distance from the vertex i to vertex j) then assign Len[j] = Len[in] + G[in][j]; and marked paths P[j] = I.

Noted: Because in C, array starting 0. Therefore, when calculating the peak will from top 0 the top n-1. However, it remains to show that is from the top 1 to n and the file input.inp the top and the top end will be calculated from 1 to n. Hence the code before we need to reduce the computation and the top end of the travel tip 1 unit. After the calculation is complete, the results when the need to increase the peak of the road looking up 1 unit to display properly (For example we want to compute the path from the top 4 to top 8, the top 4 corresponding to the position 3 in the array, top 8 corresponding position 7 so we need to reduce 4 down 3, 8 down 7 to calculate. When you find a way, assuming that 3 -> 5 -> 4 -> 7 must be in place as 4 -> 6 -> 5 -> 8).

We'll go practice according to the following chart 2 code is doing right in and follow the main content:

algorithm to find the shortest path

file input.inp: The first line is 8 point, away from the point 4 to the point 8. matrix 8×8 below is the adjacency matrix of the graph.

8 4 8
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

* Code within the main
This Code was revised and fix some bugs from code days ago (or link redundancy).

#include <stdio.h>
#include <stdlib.h>
#define INP "input.inp"
#define OUT "output.out"
 
int main() {
    FILE *fi = fopen(INP, "r");
    FILE *fo = fopen(OUT, "w");
    int n, a, b, i, sum = 0;
 
    // nhap du lieu tu file input
    fscanf(fi, "%d%d%d", &n, &a, &b);
    int G[n][n];
    int S[n], Len[n], P[n];
 
    // nhap ma tran va tinh gia tri vo cung (sum)
    for (i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            fscanf(fi, "%d", &G[i][j]);
            sum += G[i][j];
        }
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;                   // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;                       // danh sach cac diem da xet
        P[i] = a;                       // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;                         // dat do dai tu a -> a la 0
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            break;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j]) {
                i = j;
            }
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
 
    printf("done dijkstra\n");
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    printf("start find path\n");
 
    if (Len[b] > 0 && Len[b] < sum) {
        fprintf(fo, "Length of %d to %d is %d\n", a + 1, b + 1, Len[b]);
 
        // truy vet
        while (i != a) {
            fprintf(fo, "%d <-- ", i + 1);
            i = P[i];
        }
        fprintf(fo, "%d", a + 1);
    } else {
        fprintf(fo, "khong co duong di tu %d den %d\n", a + 1, b + 1);
    }
 
    printf("done find path\n");
 
    fclose(fi);
    fclose(fo);
 
    printf("done - open file output to see result\n");
    return 0;
}

thePreventive ink

* The code for each function
In the code as a function containing:
– readData implementation reads the input file.
– dijkstra implementation of algorithms
– back implementation returns the string is the way to find
– outResult implementation results in the output file

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
 
#define INP "input.inp"
#define OUT "output.out"
 
// read data in file input
int readData(int ***G, int *n, int *a, int *b) {
    FILE *fi = fopen(INP, "r");
    if (fi == NULL) {
        printf("file input not found!\n");
        return 0;
    }
    printf("start read file\n");
 
    fscanf(fi, "%d %d %d", n, a, b);
 
    *G = (int **) malloc((*n) * sizeof(int));
    for (int i = 0; i < *n; i++) {
        (*G)[i] = (int *) malloc((*n) * sizeof(int));
        for (int j = 0; j < *n; j++) {
            int x;
            fscanf(fi, "%d", &x);
            (*G)[i][j] = x;
        }
    }
 
    fclose(fi);
    printf("done read file\n");
    return 1;
}
 
// thuat toan dijkstra
int dijkstra(int **G, int n, int a, int b, int P[]) {
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start dijkstra\n");
 
    int* Len = (int *) malloc(n * sizeof(int));
    int* S = (int *) malloc(n * sizeof(int));
 
    int sum = 0;            // gia tri vo cung
 
    // tinh gia tri vo cung (sum)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += G[i][j];
        }
    }
 
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;       // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;           // danh sach cac diem da xet
        P[i] = a;           // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;             // dat do dai tu a -> a la 0
 
    int i;
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            return 0;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j])
                i = j;
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
    printf("done dijkstra\n");
    return Len[b];
}
 
//  truy vet duong di
void back(int a, int b, int *P, int n, char *path) {
 
    //char *path = (char *) malloc((n * 10) * sizeof(char));
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start find path\n");
 
    int i = b;
    int point[n];   // danh sach cac dinh cua duong di
    int count = 0;
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    point[count++] = i + 1;
    while (i != a) {
        i = P[i];
        point[count++] = i + 1;
    }
 
    strcpy(path, "");
    char temp[10];
    for (i = count - 1; i >= 0; i--) {
        sprintf(temp, "%d", point[i]);
        strcat(path, temp);
 
        if (i > 0) {
            sprintf(temp, " --> ");
            strcat(path, temp);
        }
    }
 
    printf("done find path\n");
}
 
void outResult(int len, char* path) {
    FILE *fo = fopen(OUT, "w");
 
    if (len > 0) {
        fprintf(fo, "\nLength of %c to %c is %d\n", path[0],
                path[strlen(path) - 1], len);
    }
 
    fprintf(fo, "path: %s\n", path);
 
    fclose(fo);
}
 
int main() {
    int **G, n, a, b, len;
 
    if (readData(&G, &n, &a, &b) == 0) {
        return 0;
    }
 
    char *path = (char *) malloc((10 * n) * sizeof(char));
    int P[n];
 
    len = dijkstra(G, n, a, b, P);
 
    if (len > 0) {
        back(a, b, P, n, path);
        outResult(len, path);
    } else {
        char *path = (char *) malloc((n * 10) * sizeof(char));
        sprintf(path, "khong co duong di tu %d den %d\n", a, b);
        outResult(len, path);
    }
 
    printf("done - open file output to see result\n");
    return 0;
}

link redundancy

Looking code seems a bit long, but when reading long ball tẹo then does@@=)).

2. Floyd algorithm

This algorithm allows us to find the shortest path between every pair of vertices.

If k vertices lie on the shortest path from vertex i to vertex j, the distance from i to j and from j to j is the shortest path from i to j and from j to j corresponding. Therefore we use the matrix A to save the shortest path length between every pair of vertices.
– Initially we set A[in,j] C =[in,j], A container that is initially direct path lengths (do not go over the top at all).
– Then perform n iterations, after the first iteration k, ma trận A sẽ chứa độ dài đường đi ngắn nhất giữa mọi cặp đỉnh chỉ đi qua các đỉnh thuộc tập .comment-content 1. Such, after n iterations we obtain the matrix A contains the length of the shortest path between every pair of vertices in the graph.

– Ak is the matrix notation A later iteration k, ie Ak[in,j] là độ dài đường đi ngắn nhất từ i đến j chỉ đi qua các đỉnh thuộc .comment-content 0. If[in,j] calculated according to the following formula: If[in,j] = min .comment-body 9.

– In the iterative process we have to save the trace path, ie the shortest path passing through the vertex. Then we use sub-array P[nxn], in which P[in,j] top up if k shortest path from i to j k goes through peaks. Initially P[in,j]= 0 for all i,j, because then the shortest path is the direct path, do not go over the top at all.

Code algorithm:

void Floyd (int a, int b)
{
    int max = tongthiethai();
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        {
            if (G[i][j])
                A[i][j] = G[i][j];
            else A[i][j] = max;
            P[i][j] = -1;
        }

    for (int k=0; k<n; k++)   // lap n lan
    {
        for (int i=0; i<n; i++)   // thay doi do dai duong di cua cac dinh
            for (int j=0; j<n; j++)
                if (A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    P[i][j] = k ;
                }
    }
}

How to build a complete program is similar to Dijkstra's algorithm.

Advanced Code


This is the code for selection 1 in 2 algorithms and output file in accordance with the process as the results in the picture below or backup link

file input.inp:

8
A B C D E F G H
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

Menu console
Shortest path

Output Dijkstra
Dijkstra

Output Floyd
Floyd