Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- int main(){
- int weight[10][10], visit[10], min[10], via[10];
- int i, j, k, source, dest, least, n, dd, cost = 0;
- printf("Enter Number Of Nodes: ");
- scanf("%d", &n);
- printf("Enter weights:-\n");
- for(i = 0; i < n; i++)
- for(j = 0; j < n; j++){
- printf("%c-%c: ", 'A'+i, 'A'+j);
- scanf("%d", &weight[i][j]);
- }
- for(i = 0; i < n; i++){
- visit[i] = 0;
- min[i] = 99999;
- }
- printf("Enter Source and Destination indexes:-\n");
- scanf("%d%d", &source, &dest);
- k = source;
- least = 0;
- while(visit[dest] != 2){
- visit[k] = 2;
- for(i = 0; i < n; i++){
- if(weight[k][i] && visit[i] != 2){
- dd = least + weight[k][i];
- if(dd < min[i]){
- min[i] = dd;
- via[i] = k;
- }
- visit[i] = 1;
- }
- }
- least = 99999;
- for(i = 0; i < n; i++)
- if(visit[i] == 1 && min[i] < least){
- least = min[i];
- k = i;
- }
- }
- printf("%c -> ",'A'+dest);
- cost += weight[dest][via[dest]];
- for(k = via[dest]; k != source; k = via[k]){
- printf("%c -> ",'A'+k);
- cost += weight[k][via[k]];
- }
- printf("%c",'A'+source);
- printf("\nCost = %d", cost);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement