c - 使用邻接矩阵的最宽路径问题

Question

我正在尝试制作一个应用程序来计算加权图中边缘最少的路径；但是，该图中的权重表示瓶颈，它们必须足够大以容纳作为输入传递的变量 truck_weight。我考虑过使用 Dijkstra 的修改版本来找到最大的瓶颈并从那里继续，但我不确定它是否有效。

主.c：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include "island.h"
#include "driver.h"

int main(){
    int Island [9][9] = {{0,   55,   0,   0,  44,  62,   0,   0,   0},
                        {55,    0,  98,  49, 124,   0,  85,   0,   0},
                        { 0,   98,   0,   0,   0,   0,   0, 145,   0},
                        { 0,   49,   0,   0,  75,   0, 166,   0,  53},
                        {44,  124,   0,  75,   0,   0,   0,   0,  61},
                        {62,    0,   0,   0,   0,   0,   0, 101,   0},
                        { 0,   85,   0, 166,   0,   0,   0,  61,   0},
                        { 0,    0, 145,   0,   0, 101,  61,   0,   0},
                        { 0,    0,   0,  53,  61,   0,   0,   0,   0}};
    char inserted_username[32], inserted_password[64];
    int input, market_input, inserted_truck_weight, market_weight, market_amount;
    int destination, current_node;
    struct driver *driver_head = new_driver_insertion("mario_rossi","password",40);
    struct driver *current_driver_node;
    int market_total_weight;
    while(1){
        printf("Scegli se creare un nuovo account o fare il login\n");
        printf("1. Crea un nuovo account\n");
        printf("2. Esegui il login\n");
        scanf("%d",&input);
        switch(input){
            case 1:
                printf("Inserisci il tuo username\n");
                scanf("%s",inserted_username);
                printf("Inserisci la password che intendi usare\n");
                scanf("%s",inserted_password);
                printf("Inserisci il peso del tuo camion\n");
                scanf("%d",&inserted_truck_weight);
                current_driver_node = new_driver(driver_head, inserted_username, inserted_password, inserted_truck_weight);
                input = NULL;
                break;
            case 2:
                printf("Inserisci il tuo username\n");
                scanf("%s",inserted_username);
                printf("Inserisci la tua password\n");
                scanf("%s",inserted_password);
                current_driver_node = driver_signin(driver_head, inserted_username, inserted_password);
                if(current_driver_node != NULL){
                    market_total_weight = current_driver_node->peso_camion;
                    while(market_input != 0 || market_input == NULL){
                        printf("Benvenuto nel mercato. Cosa vuoi comprare?\n");
                        printf("1. Mele    (peso =  5)\n");
                        printf("2. Banane  (peso =  4)\n");
                        printf("3. Angurie (peso = 15)\n");
                        printf("4. Arance  (peso =  6)\n");
                        printf("5. Carne   (peso = 10)\n");
                        printf("6. Pesce   (peso =  7)\n");
                        printf("7. Lattuga (peso =  8)\n");
                        printf("Premi 0 per uscire. Premi 8 per procedere al calcolo del percorso migliore, premi 9 per resettare il peso\n");
                        printf("Peso attuale del camion: %d\n", market_total_weight);
                        scanf("%d",&market_input);
                        if(market_input == 0){
                            printf("Arrivederci.\n");
                            sleep(1);
                            market_input = NULL;
                            break;
                        }else if(market_input == 8){
                            printf("Inserisci il nodo di partenza\n");
                            scanf("%d", &current_node);
                            if(current_node < 0 || current_node > 9){
                                printf("Nodo di partenza non riconosciuto.\n");
                                scanf("%d", &current_node);
                            }
                            printf("Inserisci la tua destinazione\n");
                            scanf("%d", &destination);
                            if(destination < 0 || destination > 10){
                                printf("Destinazione non riconosciuta.\n");
                                scanf("%d", &destination);
                            }
                            dijkstra_mod(Island, current_node, destination, market_total_weight);
                        }else if(market_input == 9){
                            market_total_weight = current_driver_node->peso_camion;
                            printf("Peso resettato\n");
                        }else{
                            switch(market_input){
                                case 1:
                                    market_weight = 5;
                                    break;
                                case 2:
                                    market_weight = 4;
                                    break;
                                case 3:
                                    market_weight = 15;
                                    break;
                                case 4:
                                    market_weight = 6;
                                    break;
                                case 5:
                                    market_weight = 10;
                                    break;
                                case 6:
                                    market_weight = 7;
                                    break;
                                case 7:
                                    market_weight = 8;
                                    break;
                                default:
                                    printf("Input non accettato\n");
                                    break;
                            }
                            if(market_input >= 1 && market_input <= 7){
                                printf("Quanti ne vuoi prendere?\n");
                                scanf("%d", &market_amount);
                                market_total_weight = market_total_weight + (market_weight * market_amount);
                            }
                        }
                    }
                }else{
                    printf("Le credenziali inserite sono sbagliate. Riprova.\n");
                }
                break;
            default:
                printf("Input sbagliato\n");
                break;
        }
    }
}

岛.c：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>
#include "driver.h"
#define SIZE 9

void dijkstra_mod(int Graph[SIZE][SIZE], int source, int destination, int truck_weight){
    int sptWeight[SIZE];
    bool sptSet[SIZE];
    int previous[SIZE];
    for(int i = 0; i < SIZE; i++){
        sptWeight[i] = INT_MIN;
        sptSet[i] = false;
    }
    previous[0] = -1;
    sptWeight[source] = 0;
    for(int count = 0; count < SIZE-1; count++){
        int u = maxSupportWeight(sptWeight,sptSet);
        sptSet[u] = true;
        for(int v = 0; v < SIZE; v++){
            if(!sptSet[v] && Graph[u][v] && sptWeight[u] + Graph[u][v] < sptWeight[v]){
                previous[v] = u;
                sptWeight[v] = sptWeight[u] + Graph[u][v];
            }
        }
    }
    printSolution(destination,source,previous,sptWeight);
}

int maxSupportWeight(int sptWeight[SIZE], bool sptSet[SIZE]){
    int max = INT_MIN;
    int max_index = -1;
    for(int v = 0; v < SIZE; v++){
        if(sptSet[v] == false && sptWeight[v] >= max){
            max = sptWeight[v];
            max_index = v;
        }
    }
    return max_index;
}

void printSolution(int destination, int source, int previous[SIZE], int sptWeight[SIZE]){
    printf("\n%d a %d \t\t %d\t\t%d -> ", source, destination, sptWeight[destination], source);
    printPath(previous, destination);
}

void printPath(int previous[], int j){
    while(previous[j] != -1){
        printf("%d -> ", j);
        j = previous[j];
    }
}

打印正确路径的代码不会打印正确的路径；相反，它只打印路径总瓶颈权重的地址代码以及起点和终点。不知道是不是Dijkstra修改或者路径打印功能有问题。

标签： cgraph-theory