Ghost689 2023-03-16 15:14 采纳率: 92.6%
浏览 98
已结题

c语言,修改基于第一个图的旧算法算法以解决新的问题,并将新算法用于最后一张图

有一个关于Dijkstra的无向图算法的实现,队列的处理简单,使算法的时间复杂度为𝛩(𝑛2),n是图中的节点数,将该算法应用于无向算法,下面是最初使用的加权图

img

修改算法以解决下列问题:
在一个链路网络中,有n个基站,我们可以在它们之间传输消息,一个网络包含n个互相传输信息的站点t1, t2, …, tn,由于干扰,消息可能在传输过程中被损坏。对于每一对站点,我们都知道消息被正确传输的概率(一个在0到1之间的实数)。 我们打算从t1站到tn站。设计一种算法来找到站点的路径,以最佳的概率传递消息.请注意,当一个消息通过一系列站点传输时,没有错误地传递它的概率是序列中概率的乘积。
例子,在下图中,有三个站点和给定的概率

img


通过v从t向u传递信息比直接传递信息更好,因为直接传递信息概率为0.5,而通过v的概率为0.7 × 0.8 = 0.56 > 0.50

因此,应该修改给定的算法而不是边的和。我们考虑乘积,并选择最大值(而不是像原始算法中那样的最小值)

将该算法应用于以下网络,其中边的权值为概率。该消息将从站1传送到站8,以此图用作新的算法。

img

dijkstra.不需要修改

// DSA Programming task 4.2 - Dijkstra
// You do not need to change anything here

#ifndef DIJKSTRA_H_INCLUDED
#define DIJKSTRA_H_INCLUDED

#include <limits.h>
#include <float.h>

// Maximum number of vertices
// define according to your needs
#define MAXVERTS 1000

// Nodes are numbered as integers from 1

// Maximum value in the distance table
#define INF DBL_MAX

// Defines edge in the adjacency list
typedef struct weightedgnd {
    int nodenum;
    double weight;
    struct weightedgnd* next;
} weightededgenode, *pweightededgenode;

// Defines the graph
typedef struct weightedg {
    pweightededgenode adj_list[MAXVERTS+1];
    int pred[MAXVERTS+1];
    double dist[MAXVERTS+1];
    int nVertices;
} weightedgraph;

// Initializes graph for breadth-first search
void init_graph(weightedgraph* g, int vertices);

// Adds new edge (x,y)
void add_edge(weightedgraph* g, int x, int y, double wght);

// Actual breadth-first search from node s
void dijkstra(weightedgraph* g, int s);

// Frees allocated memory
void delete_graph(weightedgraph* g, int vertices);

// Print a path after search
void print_path(weightedgraph* g, int dest);

#endif

main.c,不需要修改

// DSA Programming task 4.2 - Dijkstra
// You do not need to change anything here

#include <stdio.h>
#include "dijkstra.h"

int main(){
    weightedgraph g;
    init_graph(&g,8);

    add_edge(&g,1,2,1);
    add_edge(&g,1,4,7);
    add_edge(&g,1,5,3);

    add_edge(&g,2,3,1);
    add_edge(&g,3,4,2);
    add_edge(&g,5,6,3);

    add_edge(&g,6,7,3);
    add_edge(&g,6,8,3);

    // The other graph
    add_edge(&g,2,4,2);
    add_edge(&g,4,6,2);

    dijkstra(&g,1);

    printf("The path from 1 to 8 with cumulative weights:\n");
    print_path(&g,8);

    delete_graph(&g,8);

    return 0;
}

dijkstra.c只对有TODO的部分进行修改(即为void init_graph函数的TODO部分和void dijkstra的TODO部分),具体修改要求详情见代码部分的注释

// DSA Programming task 4.2 - Dijsktra
// You work on this file where TODO is located
#include <stdio.h>
#include <stdlib.h>
#include "dijkstra.h"

// Initializes graph for Dijkstra
void init_graph(weightedgraph* g, int vertices){
    g->nVertices = vertices;
    int i;
    for(i=1; i <= vertices; i++) {
        g->adj_list[i] = 0;
        g->pred[i] = 0;
        // TODO! Note the distance
        g->dist[i] = INF;
    }
}

// Adds new edge (x,y)
void add_edge(weightedgraph* g, int x, int y, double wght){
    if( x <= g->nVertices && y <= g->nVertices){
        pweightededgenode pxy = malloc(sizeof(weightededgenode));
        pweightededgenode pyx = malloc(sizeof(weightededgenode));

        pxy->nodenum = y;
        pxy->next = g->adj_list[x];
        pxy->weight = wght;
        g->adj_list[x] = pxy;

        pyx->nodenum = x;
        pyx->next = g->adj_list[y];
        pyx->weight = wght;
        g->adj_list[y] = pyx;
    }
}


/*
   Dijkstra's algorithm:
   DIJKSTRA(G,w,s)
   for each vertex v in V
      d[v] = INF
      p[v] = NIL
   d[s] = 0
   S = EMPTY
   Q = V[G]
   while Q != EMPTY
         u =  EXTRACT-MIN(Q)
         S = S UNION {u}
         for each vertex v in Adj[u] do
            if d[v] > d[u] + w(u,v) then
               d[v] = d[u] + w(u,v)
               p[v] = u
*/

// Dijkstra search from node s
void dijkstra(weightedgraph* g, int s){
    int queue[MAXVERTS];
    int i=0;

    // Initialize graph
    for(i=1; i <= g->nVertices; i++) {
        g->pred[i] = 0;
        g->dist[i] = INF;
        // All vertices in queue
        queue[i] = i;
    }

    // TODO! Modification should start from here
    //       Note that the propability should be maximized
    //       Chanage names of variables accordingly
    g->dist[s] = 0;

    for(i=g->nVertices; i >= 1; i--) {
        // Search for minimum from the queue
        double minval = g->dist[queue[1]];
        int minnode = queue[1];
        int minj=1;
        for(int j = 1; j <= i; j++) {
            if( g->dist[queue[j]] < minval ){
                minval = g->dist[queue[j]];
                minnode = queue[j];
                minj = j;
            }
        }

        // Switches the minimum to end (out of the queue)
        int temp = queue[i];
        queue[i] = queue[minj];
        queue[minj] = temp;

        pweightededgenode pedge = g->adj_list[minnode];

        // Relax the neighbors
        while(pedge != 0){
            int v = pedge->nodenum;
            if(g->dist[v] > (g->dist[minnode]+pedge->weight))  {
                g->dist[v] = g->dist[minnode]+pedge->weight;
                g->pred[v] = minnode;
            }
            pedge = pedge->next;
        }

        // DEBUG INFO:
        // printf("%d processed: d[%d] = %f\n",minnode,minnode,g->dist[minnode]);
    }
}
//No need to change anyting after this point!

// Free allocated memory
void delete_graph(weightedgraph* g, int vertices){
    int i;
    for(i=1; i <= vertices; i++) {
        pweightededgenode pedge = g->adj_list[i];
        pweightededgenode pnext = 0;

        while(pedge != 0) {
            pnext = pedge->next;
            free(pedge);
            pedge = pnext;
        }
    }
}

// Print a path after search
void print_path(weightedgraph* g, int dest){
    if( g->pred[dest] != 0){
        print_path(g, g->pred[dest]);
        printf("%d:%f\n",dest,g->dist[dest]);
    }
    else if(g->dist[dest]==0){
        printf("%d:%f\n",dest,g->dist[dest]);
    }
}



  • 写回答

3条回答 默认 最新

  • 代码的天敌是懒惰 2023-03-16 16:58
    关注

    基于最新版ChatGPT4的回答,望采纳!!!有其他问题也可以询问我哦、”(最新版更智能,功能更加强大)

    为了解决这个问题,我们需要修改Dijkstra算法,使其最大化概率乘积而不是最小化权重和。我们将进行以下更改:

    1. 初始化时,将源节点的距离设置为1,而不是0。
    2. 在寻找最小距离的节点时,寻找具有最大距离的节点。
    3. 在更新节点的距离时,使用概率乘积而不是权重和。

    以下是修改后的dijkstra.c文件中的代码:

    // DSA Programming task 4.2 - Dijsktra
    // You work on this file where TODO is located
    #include <stdio.h>
    #include <stdlib.h>
    #include "dijkstra.h"
    
    // Initializes graph for Dijkstra
    void init_graph(weightedgraph* g, int vertices){
        g->nVertices = vertices;
        int i;
        for(i=1; i <= vertices; i++) {
            g->adj_list[i] = 0;
            g->pred[i] = 0;
            // TODO! Note the distance
            g->dist[i] = 0.0;
        }
    }
    
    // ...
    
    // Dijkstra search from node s
    void dijkstra(weightedgraph* g, int s){
        int queue[MAXVERTS];
        int i=0;
    
        // Initialize graph
        for(i=1; i <= g->nVertices; i++) {
            g->pred[i] = 0;
            g->dist[i] = 0.0;
            // All vertices in queue
            queue[i] = i;
        }
    
        // TODO! Modification should start from here
        //       Note that the propability should be maximized
        //       Chanage names of variables accordingly
        g->dist[s] = 1.0;
    
        for(i=g->nVertices; i >= 1; i--) {
            // Search for maximum from the queue
            double maxval = g->dist[queue[1]];
            int maxnode = queue[1];
            int maxj=1;
            for(int j = 1; j <= i; j++) {
                if( g->dist[queue[j]] > maxval ){
                    maxval = g->dist[queue[j]];
                    maxnode = queue[j];
                    maxj = j;
                }
            }
    
            // Switches the maximum to end (out of the queue)
            int temp = queue[i];
            queue[i] = queue[maxj];
            queue[maxj] = temp;
    
            pweightededgenode pedge = g->adj_list[maxnode];
    
            // Relax the neighbors
            while(pedge != 0){
                int v = pedge->nodenum;
                if(g->dist[v] < (g->dist[maxnode]*pedge->weight))  {
                    g->dist[v] = g->dist[maxnode]*pedge->weight;
                    g->pred[v] = maxnode;
                }
                pedge = pedge->next;
            }
    
            // DEBUG INFO:
            // printf("%d processed: d[%d] = %f\n",maxnode,maxnode,g->dist[maxnode]);
        }
    }
    //No need to change anyting after this point!
    
    // ...
    

    使用此修改后的算法,您将能够找到具有最佳概率传递消息的路径。在给定示例中,该算法将找到从站1到站8的最佳路径。我们将使用修改过的Dijkstra算法计算给定图中从节点1到节点8的最佳传输路径。请确保您使用了上述提供的修改后的dijkstra.c文件代码。使用此修改后的算法,您可以通过运行main.c文件找到所需的路径。

    现在,我们已经修改了Dijkstra算法以解决您的问题,您可以运行main.c文件,以找到从站1到站8的最佳传输路径。在您提供的示例中,该算法将找到具有最佳概率传递消息的路径。

    请注意,修改后的Dijkstra算法可以适用于您的问题。但是,在特定情况下,这种方法可能不是最有效的。例如,对于具有大量节点和边的大型网络,这种方法可能需要更多的计算资源和时间。在这种情况下,可以考虑使用其他更高效的算法,如A*搜索算法或其他启发式搜索方法。

    如果您有其他关于Dijkstra算法或其他算法的问题,请随时提问。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月24日
  • 已采纳回答 3月16日
  • 修改了问题 3月16日
  • 修改了问题 3月16日
  • 展开全部

悬赏问题

  • ¥15 halcon DrawRegion 提示错误
  • ¥15 FastAPI Uvicorn启动显示404
  • ¥15 centos7.9脚本,怎么排除特定的访问记录
  • ¥15 关于#Django#的问题:我的静态文件呢?
  • ¥15 关于CPLEX的问题,请专家解答
  • ¥15 cocos的点击事件 怎么穿透到 原生fragment上。
  • ¥20 基于相关估计的TDOA算法中的加权最小二乘拟合法matlab仿真
  • ¥20 基于相关估计的TDOA算法中的自适应加权广义互相关法。
  • ¥15 abaqus CAE 2024软件启动问题
  • ¥20 基于相关估计的TDOA算法中的局部互相关函数滤波matlab仿真