The shortest path problem of a graph

Description

The weather is getting colder. The old and frail Yueyue bird plans to spend the winter in a city with appropriate temperature in the south. However, due to the serious aging of its wings, the farthest flight distance is limited. Please calculate the shortest distance required for the poor Yueyue bird so that it can be psychologically prepared.

Input

The input contains multiple sets of test data.

The first line of each group is two positive integers n (n < = 20) and m (m < = n * (n-1) / 2). N represents the number of cities and M represents the number of line segments. (the line segment is the connecting line between two cities)

Next m lines, input three integers a, B, and l (L < = 10 ^ 9) in each line, indicating that there is a line segment between city a and city B, and the length of the line segment is L. (a is different from b)

Enter two integers x and y in the last line of each group to represent the problem: X is the city where Yueyue bird is now, and y is the city where Yueyue bird plans to fly to spend the winter. The city label is 1~n.

Output

For each group of inputs, output the shortest distance between city x and city y. if city x and city y are not connected, output "No path".

Samples

input Copy

4 4 1 2 4 1 3 1 1 4 1 2 3 1 2 4

output Copy

3

Dijkstra

Dijestra algorithm is used to find the shortest path from one vertex to other vertices, which is just suitable for this problem

thinking

In the dijestra algorithm, we need to maintain a found array, where found[i] indicates whether the shortest path to point I has been found, and also maintain a distance array, where distance[i] indicates the shortest path to point I. Each time, find out the point with the shortest path from the point where the shortest path has never been found, and then mark it as found. Then start from it to explore whether there is a path to other nodes. If there is a path and it is shorter than the current one, update the distance array

code

#include"iostream"
using namespace std;

#define max 1000000000

int graph[50][50];
int find(int dis[], int s[],int n){
    int min=max;
    int minpos=-1;
    for(int i=1; i <= n; i++){
        if(dis[i] < min && s[i]==0){
            min = dis[i];
            minpos = i;
        }
    }
    return minpos;
}
int main(){
    int n,m;
    while(cin>>n>>m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j] = max;
            }
        }

        for (int i = 1; i <= n; i++) {
            graph[i][i] = 0;
        }

        while (m--) {
            int a, b, l;
            cin >> a >> b >> l;
            graph[a][b] = graph[b][a] = l;
        }
        int x, y;
        cin >> x >> y;
        int dis[n + 1];
        int s[n + 1];
        for (int i = 1; i <= n; i++) {
            dis[i] = graph[x][i];
            s[i]=0;
        }
        int u;
        s[x] = 1;
        while (u = find(dis, s, n), u != -1) {
            s[u] = 1;
            for (int w = 1; w <= n; w++) {
                if (dis[u] + graph[u][w] < dis[w]) {
                    dis[w] = dis[u] + graph[u][w];
                }
            }
        }
        if (dis[y] == max) {
            cout << "No path" << endl;
        } else {
            cout << dis[y] << endl;
        }
    }
}

The complexity of this algorithm is n ^ 2

Floyd algorithm

Floyd algorithm is an algorithm for finding the distance between any two points in a graph

thinking

Floyd algorithm is to select a vertex from the adjacency matrix every time, then traverse the two vertices i and j in the matrix, and compare the distance between i - > J and i - > k plus K - > J

Floyd algorithm is violent and easy to remember

#include"iostream"
#include"set"
#include"vector"
#include"algorithm"
using namespace std;


int main(){
    int n,m;
    while(cin>>n>>m) {
        vector<vector<int> > graph(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j)graph[i][j] = 1000000000;
                else graph[i][j] = 0;
            }
        }
        while (m--) {
            int a, b, l;
            cin >> a >> b >> l;
            graph[a][b] = graph[b][a] = l;
        }
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
        int x, y;
        cin >> x >> y;
        if (graph[x][y] == 1000000000) {
            cout << "No path" << endl;
        } else {
            cout << graph[x][y] << endl;
        }
    }
}

These three for loops tell us that its time complexity is O(n^3). Although it is a little slow, it is easy to remember.